UVA11248_Frequency Hopping

给一个有向网络，求其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=;

bool can[maxn];

int Q[maxn],bot,top;

int n,m,cmax,s,t,cas=;

vector<pr> ans;

void _init()

{

    edge=-;

    s=,t=n;

    for (int i=; i<=n; i++) first[i]=-;

}

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]=,next[edge]=first[V],first[V]=edge;

}

bool bfs()

{

    Q[bot=top=]=t,d[t]=,tag[t]=++TAG,can[t]=false;

    while (bot<=top)

    {

        int cur=Q[bot++];

        for (int i=first[cur]; i!=-; i=next[i])

            if (c[i^]> && tag[to[i]]!=TAG)

            {

                d[to[i]]=d[cur]+,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!=-; i=next[i])

        if (c[i]> && tag[to[i]]==TAG && d[to[i]]==d[cur]- && !can[to[i]])

        {

            k=dfs(to[i],min(num,c[i]));

            if (k) num-=k,c[i]-=k,c[i^]+=k;

            if (!num) break;

        }

    if (num) can[cur]=true;

    return tmp-num;

}

int maxflow()

{

    int flow=;

    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=; 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=; i<=edge; i++) C[i]=c[i];

        for (int i=; i<=edge; i+=)

        {

            if (c[i]+c[i+]>cmax) continue;

            c[i]+=cmax-last-c[i];

            if (last+maxflow()>=cmax) ans.push_back(mp(to[i+],to[i]));

            for (int j=; j<=edge; j++) c[j]=C[j];

        }

        if (ans.size()==) puts("not possible");

        else

        {

            sort(ans.begin(),ans.end());

            printf("possible option:(%d,%d)",ans[].first,ans[].second);

            for (unsigned i=; i<ans.size(); i++)

                printf(",(%d,%d)",ans[i].first,ans[i].second);

            printf("\n");

        }

    }

    return ;

}