网络流24题中最水的一题， 难点在于输出路径，但跑完Dinic后在存的图中找反向边，查看是否有流量即可判断是否连边
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <map> #include <queue> #include <functional> #include <vector> #include <stack> #include <set> #include <bitset> using namespace std; typedef long long ll; const int maxn=200+50; const int inf=0x7fffffff; const int MOD=998244353; const int HASH=131; int n, m, cnt;//点，边，前向星计数 int head[maxn];//前向星 int level[maxn];//分层 int cur[maxn];//当前弧优化 struct Edge { int to; ll val; int next; }edge[maxn*maxn]; void add(int u,int v,int val) { edge[cnt].to=v; edge[cnt].val=val; edge[cnt].next=head[u]; head[u]=cnt++; /*反向存边，在原边基础上+1*/ edge[cnt].to=u; edge[cnt].val=0; edge[cnt].next=head[v]; head[v]=cnt++; } bool find_level(int s,int t)//源点和汇点,该bfs函数用来确定深度（层次） { queue<int> q; memset(level,0,sizeof(level)); for(int i=1;i<=n;i++) { cur[i]=head[i]; } int u=s; level[u]=1; q.push(u); while(!q.empty()) { u=q.front(); q.pop(); for(int i=head[u];~i;i=edge[i].next) { int v=edge[i].to; ll val=edge[i].val; if(!level[v]&&val)//层次不为0且容量不为0 { level[v]=level[u]+1; q.push(v); } } if(level[t])//如果t有分层则继续下一步的处理 { return true; } } return false; } ll updata(int u,ll u_val,int t)//dfs更新 { if(u==t) { return u_val; } ll used=0;//使用多少容量 for(int &i=cur[u];~i;i=edge[i].next)//当前弧优化的神奇操作 { int v=edge[i].to; ll val=edge[i].val; if(level[v]==level[u]+1&&val)//如果是相邻两层且有剩余容量 { ll tmp=updata(v,min(u_val-used,val),t);//dfs递归，找最小容量 edge[i].val-=tmp; edge[i^1].val+=tmp; used+=tmp; if(used==u_val) { return used;//达到最大值，本条增广路作废？ } } } if(used==0) level[u]=-1;//找不到增广路，减枝,节点作废 return used; } ll Dinic(int s,int t) { ll ans=0; while(find_level(s,t)) { ans+=updata(s,inf,t); } return ans; } void init() { cnt=0; memset(head,-1,sizeof(head)); } int main() { init(); int s,t; cin>>m>>n; int u,v; int res=n-m; s=1; t=n+2; for(int i=1;i<=m;i++) add(1,i+1,1); for(int i=m+1;i<=n;i++) add(i+1,t,1); while(scanf("%d %d",&u,&v)!=EOF&&(u!=-1&&v!=-1)) { add(u+1,v+1,1); } n=t; int tot=Dinic(s,t); if(!tot) { cout<<"No Solution!"<<endl; } else { cout<<tot<<endl; for(int i=2;i<cnt;i+=2) if(edge[i].to!=s&&edge[i^1].to!=s&&edge[i].to!=t&&edge[i^1].to!=t) { if(edge[i^1].val!=0) { cout<<edge[i^1].to-1<<' '<<edge[i].to-1<<endl; } } } return 0; }