首页 > 代码库 > UVA11248_Frequency Hopping

UVA11248_Frequency Hopping

2024-07-13 17:37:16   216人阅读

给一个有向网络，求其1,n两点的最大流量是否不小于C，如果小于，是否可以通过修改一条边的容量使得最大流量不小于C？

首先对于给定的网络，我们可以先跑一遍最大流，然后先看流量是否大于C。

然后保存跑完第一次最大流后的残余网络容量情况，然后接下来对于每条割，将分别其容量加C-maxflow,看看能否得到满足条件的流量即可。

 

 

召唤代码君：

 

 

#include <iostream>#include <cstring>#include <cstdio>#include <vector>#include <algorithm>#define maxn 1110#define maxm 222220#define mp(x,y) make_pair(x,y)using namespace std;typedef pair<int,int> pr;int C[maxm];int to[maxm],next[maxm],c[maxm],first[maxn],edge;int d[maxn],tag[maxn],TAG=222;bool can[maxn];int Q[maxn],bot,top;int n,m,cmax,s,t,cas=0;vector<pr> ans;void _init(){    edge=-1;    s=1,t=n;    for (int i=1; i<=n; i++) first[i]=-1;}void addedge(int U,int V,int W){    edge++;    to[edge]=V,c[edge]=W,next[edge]=first[U],first[U]=edge;    edge++;    to[edge]=U,c[edge]=0,next[edge]=first[V],first[V]=edge;}bool bfs(){    Q[bot=top=1]=t,d[t]=0,tag[t]=++TAG,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)            {                d[to[i]]=d[cur]+1,Q[++top]=to[i];                can[to[i]]=false,tag[to[i]]=TAG;                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=first[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()) flow+=dfs(s,cmax);    return flow;}int main(){    int U,V,W,last;    while (scanf("%d%d%d",&n,&m,&cmax) && (n))    {        _init();        for (int i=1; i<=m; i++)        {            scanf("%d%d%d",&U,&V,&W);            addedge(U,V,W);        }        printf("Case %d: ",++cas);        last=maxflow();        if (last>=cmax)        {            puts("possible");            continue;        }        ans.clear();        for (int i=0; i<=edge; i++) C[i]=c[i];        for (int i=0; i<=edge; i+=2)        {            if (c[i]+c[i+1]>cmax) continue;            c[i]+=cmax-last-c[i];            if (last+maxflow()>=cmax) ans.push_back(mp(to[i+1],to[i]));            for (int j=0; j<=edge; j++) c[j]=C[j];        }        if (ans.size()==0) puts("not possible");        else        {            sort(ans.begin(),ans.end());            printf("possible option:(%d,%d)",ans[0].first,ans[0].second);            for (unsigned i=1; i<ans.size(); i++)                printf(",(%d,%d)",ans[i].first,ans[i].second);            printf("\n");        }    }    return 0;}


联系
我们