首页 > 代码库 > ZOJ3792_Romantic Value

ZOJ3792_Romantic Value

2024-07-16 01:13:40   218人阅读

给出图，使得两点无流量，剩余其他边的总容量与删除边数的比值。

要机智啊。。。

因为原图给的边数不超过1000，容量也不超过1000，可以这样把边的容量变为2000*c+1。这样跑出最大流后，最大流除以2000就是最大流，最大流模2000就是所求的边割了。。。

 

 

 

召唤代码君：

 

 

#include <iostream>#include <cstring>#include <cstdio>#include <vector>#define maxn 111#define maxm 2222using namespace std;const int inf=~0U>>2;int to[maxm],c[maxm],next[maxm],first[maxn],work[maxn],edge;int Q[maxm],tag[maxn],d[maxn],bot,top,TAG=222;bool can[maxn];int n,m,s,t,T,ans,cur,hehe,num,tot_v,last;vector<int> TO[maxn];void _init(){    edge=tot_v=0;    memset(first,-1,sizeof(int)*(n+2));    for (int i=1; i<=n; i++) TO[i].clear();}void addedge(int U,int V,int W){    to[edge]=V,c[edge]=W,next[edge]=first[U],first[U]=edge++;    to[edge]=U,c[edge]=W,next[edge]=first[V],first[V]=edge++;}void addedge2(int U,int V,int W){    cout<<" addedge 2 : "<<U<<‘ ‘<<V<<‘ ‘<<W<<endl;    to[edge]=V,c[edge]=W,next[edge]=first[U],first[U]=edge++;    to[edge]=U,c[edge]=0,next[edge]=first[V],first[V]=edge++;}bool bfs(){    Q[bot=top=1]=t,tag[t]=++TAG,d[t]=0,can[t]=false;    while (bot<=top)    {        int cur=Q[bot++];        for (int i=first[cur]; i!=-1; i=next[i])            if (c[i^1]>0 && tag[to[i]]!=TAG)            {                tag[to[i]]=TAG,d[to[i]]=d[cur]+1;                can[to[i]]=false,Q[++top]=to[i];                if (to[i]==s) return true;            }    }    return false;}int dfs(int cur,int num){    if (cur==t) return num;    int tmp=num,k;    for (int& i=work[cur]; i!=-1; i=next[i])        if (c[i]>0 && tag[to[i]]==TAG && d[to[i]]==d[cur]-1 && !can[to[i]])        {            k=dfs(to[i],min(num,c[i]));            if (k) num-=k,c[i]-=k,c[i^1]+=k;            if (!num) break;        }    if (num) can[cur]=true;    return tmp-num;}int maxflow(){    int Flow=0;    while (bfs()){        memcpy(work,first,sizeof(int)*(n+2));        Flow+=dfs(s,inf);    }    return Flow;}void bfs(int cur){    for (int i=first[cur] ;i!=-1; i=next[i])        if (c[i]==0 && c[i^1]>0){            TO[cur].push_back(to[i]);            bfs(to[i]);        }}int main(){    int U,V,W;    scanf("%d",&T);    while (T--){        scanf("%d%d%d%d",&n,&m,&s,&t);        _init();        while (m--){            scanf("%d%d%d",&U,&V,&W);            tot_v+=W;            addedge(U,V,W*2000+1);        }        hehe=ans=maxflow();        if (ans==0){            printf("Inf\n");            continue;        }        //cout<<tot_v<<‘ ‘<<ans<<‘ ‘<<num<<endl;        printf("%.2f\n",(tot_v-ans/2000)/(1.0*(ans%2000)));    }    return 0;}

 


联系
我们