【題解】cycle
題目描述
給定一個無向圖,求一個環,使得環内邊權\(\div\)環内點數最大。
資料範圍
\(n \le 5000\) \(m\le 10000\)
\(Solution\)
考慮到我們可以對答案的式子變一下形,
\(\frac{\Sigma_{i\in V'} w_i}{|V'|}\le ans\)
\(\Sigma_{i\in V'}w_i-ans\times |V'|\le0\)
這一步不要看不懂了(\(i\)共有\(|V'|\)個,是以\(ans\)仍然總共被加了\(|V'|\)次):
\(\Sigma_{i\in V'} (w_i-ans) \le 0\)
即
\(\Sigma_{i \in V'} w'_i\le0\)
直接\(spfa\)跑負環就好了。
實際上這是一個很有用的方法,先根據題目答案的意義判斷是否存在答案單調性,再通過數學變換得到我們想要的式子。
或者感性了解,我們得到一堆邊的平均邊權是\(ans\)了,那麼這個邊集的所有權減去這個\(ans\)然後加起來一定等于\(0\)。假如加起來比\(0\)大,說明不存在,假設比這個小,說明有更優解。
上好看的代碼qvq
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
#define DRP(t,a,b) for(register int t=(a),edd=(b);t>=edd;--t)
#define RP(t,a,b) for(register int t=(a),edd=(b);t<=edd;++t)
#define ERP(t,a) for(register int t=head[a];t;t=e[t].nx)
#define midd register int mid=(l+r)>>1
#define TMP template < class ccf >
TMP inline ccf qr(ccf b){
register char c=getchar();register int q=1;register ccf x=0;
while(c<48||c>57)q=c==45?-1:q,c=getchar();
while(c>=48&&c<=57)x=x*10+c-48,c=getchar();
return q==-1?-x:x;}
TMP inline ccf Max(ccf a,ccf b){return a<b?b:a;}
TMP inline ccf Min(ccf a,ccf b){return a<b?a:b;}
TMP inline ccf Max(ccf a,ccf b,ccf c){return Max(a,Max(b,c));}
TMP inline ccf Min(ccf a,ccf b,ccf c){return Min(a,Min(b,c));}
TMP inline ccf READ(ccf* _arr,int _n){RP(t,1,_n)_arr[t]=qr((ccf)1);}
//----------------------template&IO---------------------------
const int maxn=3e3+15;
const int maxm=1e4+15;
struct E{
int to,nx;
long double w;
}e[maxm];
const long double EPS=1e-10;
int head[maxn];
int usd[maxn];
bool in[maxn];
double d[maxn];
double sa[maxm];
int cnt;
int n,m;
inline void add(int fr,int to,long double w){
cnt++;
e[cnt].to=to;
e[cnt].nx=head[fr];
e[cnt].w=w;
sa[cnt]=w;
head[fr]=cnt;
}
bool c=0;
void spfa(int now){
if(c) return;
usd[now]=1;
ERP(t,now){
if(d[e[t].to]>d[now]+e[t].w){
d[e[t].to]=d[now]+e[t].w;
if(c||usd[e[t].to]) return void(c=1);
spfa(e[t].to);
}
}
usd[now]=0;
}
inline bool chek(long double x){
RP(t,1,m) e[t].w=sa[t]-x;
RP(t,1,n) usd[t]=d[t]=0;c=0;
RP(t,1,n) if(!usd[t]) spfa(t);
return c;
}
int main(){
n=qr(1);m=qr(1);
int t1,t2;
long double t3;
long double l=-1e7-(long double)1,r=1e7+(long double)1;
long double mid;
RP(t,1,m){
t1=qr(1);t2=qr(1);
scanf("%Lf",&t3);
add(t1,t2,t3);
}
do{
mid=(l+r)/(long double)2;
if(chek(mid))
r=mid;
else
l=mid;
}while(l+EPS<r);
printf("%.8Lf\n",l);
return 0;
}
/*
dfs序+樹連剖腹
亂做
orz yyb
不行 有情況沒有考慮到!
直接tarjin
二分就好了吧 亂做OK
不行 我是****
*/
轉載于:https://www.cnblogs.com/winlere/p/10367960.html