本文参考自: 原文地址
UVA 11248.
题意：给定一个有向网络，每条边均有一个容量。问是否存在一个从点1到点N，流量为C的流，如果不存在，是否可以恰好修改一条弧的容量，使得存在这样的流。
思路：先求一次最大流，如果中途就大于等于C或者结尾大于等于C，就直接输出，如果小于C，就需要修改最小割里的弧，依次把最小割里的弧加上C再求最大流与C去比较就行了。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int maxn=101;
struct Edge{int from,to,cap,flow;
};
int c,sum,kase=0;
struct node
{int u,v;
};
bool cmp(node c,node d)
{if(c.u==d.u)return c.v<d.v;return c.u<d.u;
}
struct Dinic
{int n,s,t;vector<Edge>edges;vector<int>G[maxn];bool vis[maxn];int d[maxn];int cur[maxn];void init(int n,int m){this->n=n;sum=0; }void AddEdge(int from,int to,int cap){edges.push_back((Edge){from,to,cap,0});edges.push_back((Edge){to,from,0,0});int m=edges.size();G[from].push_back(m-2);G[to].push_back(m-1);}bool BFS(){memset(vis,0,sizeof(vis));memset(d,0,sizeof(d));memset(cur,0,sizeof(cur));queue<int>Q;Q.push(s);d[s]=0;vis[s]=1;while(!Q.empty()){int x=Q.front();Q.pop();for(int i=0;i<G[x].size();i++){Edge& e=edges[G[x][i]];if(!vis[e.to]&&e.cap>e.flow){vis[e.to]=1;d[e.to]=d[x]+1;Q.push(e.to);}}}return d[t];}int DFS(int x,int a){if(x==t||a==0)return a;int flow=0,f;for(int& i=cur[x];i<G[x].size();i++){Edge& e=edges[G[x][i]];if(d[x]+1==d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0){e.flow+=f;edges[G[x][i]^1].flow-=f;flow+=f;a-=f;if(flow+sum>=c)return c;if(a==0)break;}}return flow;}int Maxflow(int s,int t){this->s=s,this->t=t;int flow=0;while(BFS()){flow+=DFS(s,c);if(flow+sum>=c)return c;}return flow; }vector<int>Mincut(){vector<int>tmp;for(int i=0;i<edges.size();i++)if(vis[edges[i].from]&&!vis[edges[i].to]&&edges[i].cap>0)tmp.push_back(i);return tmp;}void rebuild(){for(int i=0;i<edges.size();i++)edges[i].cap-=edges[i].flow;}void flowclear(){for(int i=0;i<edges.size();i++)edges[i].flow=0;}void work(){sum=Maxflow(1,n);printf("Case %d: ",++kase);if(sum>=c)printf("possible\n");else{vector<int>cut=Mincut();rebuild();vector<node>ans;for(int i=0;i<cut.size();i++){edges[cut[i]].cap=c;flowclear();if(sum+Maxflow(1,n)>=c)ans.push_back((node){edges[cut[i]].from,edges[cut[i]].to});edges[cut[i]].cap=0;}if(ans.size()==0)printf("not possible\n");else{sort(ans.begin(),ans.end(),cmp);printf("possible option:(%d,%d)",ans[0].u,ans[0].v);for(int i=1;i<ans.size();i++)printf(",(%d,%d)",ans[i].u,ans[i].v);printf("\n") ;}} edges.clear();for(int i=0;i<=n;i++)G[i].clear(); }
};
Dinic solve;
int main()
{int n,m,u,v,cap;while(~scanf("%d%d%d",&n,&m,&c)&&n+m+c) {solve.init(n,m);for(int i=1;i<=m;i++){scanf("%d%d%d",&u,&v,&cap);solve.AddEdge(u,v,cap);}solve.work();}
}