题目链接：

 

题意：给定一个有向网络，每条边均有一个容量。问是否存在一个从点1到点N，流量为C的流。如果不存在，是否可以恰好修改一条弧的容量，使得存在这样的流？

 

分析：

首先找到最大流，如果发现大于等于C，就得到解，如果小于C的话，枚举最小割。这时，之前的最大流保存下来，清空流量，改变最小割的容量，再求最大流。

 

include 
     
      using namespace std;const int maxn = 100 + 10;const int INF = 0x3f3f3f3f;struct Edge {    int from,to,cap,flow;};bool operator < (const Edge& a,const Edge& b) {    return a.from < b.from || (a.from==b.from&&a.to
      
        edges;    vector
       
         G[maxn];    bool vis[maxn];    int d[maxn];    int cur[maxn];    void init(int n) {        for(int i=0;i
        

Q; Q.push(s); vis[s] = 1; d[s] = 0; while(!Q.empty()) { int x = Q.front(); Q.pop(); for(int i=0;i

e.flow) { vis[e.to] = 1; d[e.to] = d[x] + 1; Q.push(e.to); } } } return vis[t]; } int DFS(int x,int a) { if(x==t||a==0) return a; int flow =0,f; for(int& i=cur[x];i

0) { e.flow +=f; edges[G[x][i]^1].flow -=f; flow +=f; a-=f; if(a==0) break; } } return flow; } int Maxflow(int s,int t) { this->s = s; this->t = t; int flow = 0; while(BFS()) { memset(cur,0,sizeof(cur)); flow +=DFS(s,INF); } return flow; } vector

Mincut() { vector

ans; for(int i=0;i

0) ans.push_back(i); } return ans; } void Reduce () { for(int i=0;i

=c) printf("possible\n"); else { vector

cut = g.Mincut(); g.Reduce(); vector

ans; for(int i=0;i

=c) ans.push_back(e); e.cap = temp; /// } if(ans.empty()) printf("not possible\n"); else { sort(ans.begin(),ans.end()); printf("possible option:(%d,%d)",ans[0].from+1,ans[0].to + 1); for(int i=1;i