题目链接：点击打开链接
题意：给定一个图包含n个点，m条容量为1的有向边，，问只翻转一条边能使s到t的最大流增大到多少？有多少种方法？
思路：先跑一遍最大流，在残余流量里把点分为为两个集合，第一个集合包含所有从起点能到达的点，第二个集合包含所有能到达终点的点，那么答案就是起点在第二个集合终点在第一个集合的边的条数（两个集合都不包含的点忽略）。
cpp代码：
#include <cstdio>#include <iostream>#include <cstring>#include <string>#include <algorithm>#include <cmath>#include <map>#include <vector>#include <bitset>#include <queue>using namespace std;#define maxn 10010#define INF 1e9struct Edge{int from,to,cap,flow;};struct Dinic{int n,m,s,t;vector<Edge> edges;vector<int> G[maxn],g[maxn];vector<Edge> ed;bool vis[maxn] ;int d[maxn];int cur[maxn];int un[maxn];void add(int a,int b){edges.push_back((Edge){a,b,1,0});edges.push_back((Edge){b,a,0,0});m=edges.size();g[b].push_back(m-2);g[a].push_back(m-1);G[a].push_back(m-2);G[b].push_back(m-1);}bool bfs(){memset(vis,0,sizeof(vis));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 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<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(a==0) break;}}return flow;}int max_flow(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;}void ddfs(int s,int bj){if(bj==1){un[s]=bj;for(int i=0;i<G[s].size();i++){if(!un[edges[G[s][i]].to]&&edges[G[s][i]].flow<edges[G[s][i]].cap)ddfs(edges[G[s][i]].to,bj);}}else {un[s]=bj;for(int i=0;i<g[s].size();i++){if(!un[edges[g[s][i]].from]&&edges[g[s][i]].flow<edges[g[s][i]].cap)ddfs(edges[g[s][i]].from,bj);}}}int solve(){int cnt=0;memset(un,0,sizeof(un));ddfs(s,1);ddfs(t,2);for(int i=0;i<edges.size();i+=2){//cout<<edges[i].from<<" "<<edges[i].to<<" "<<edges[i].flow<<" "<<un[edges[i].from]<<" "<<un[edges[i].to]<<endl;if(un[edges[i].to]==1&&un[edges[i].from]==2&&edges[i].flow<edges[i].cap)cnt++;}return cnt;}};int main(){//freopen("data.in","r",stdin);int n,m,s,t;int ta,tb;while(~scanf("%d%d%d%d",&n,&m,&s,&t)){Dinic M;if(n==0&&m==0&&s==0&&t==0) break;for(int i=0;i<m;i++){scanf("%d%d",&ta,&tb);M.add(ta,tb);}int ans=M.max_flow(s,t);int tp=M.solve();if(tp) ans++;cout<<ans<<" "<<tp<<endl;}return 0;}
接受失败，是我们不常听到或看到的一个命题，
