题面
https://www.luogu.org/problem/P2756
题解
#include<cstdio> #include<cstring> #include<iostream> #include<vector> #include<queue> #define ri register int #define N 300 #define INF 1000000007 #define M 25000 using namespace std; int n,m; struct Dinic { vector<int> ed[N]; int w[M],to[M],d[N],cur[N]; int cnt; void init() {cnt=-1;} void add_edge(int a,int b,int c) { ed[a].push_back(++cnt); w[cnt]=c; to[cnt]=b; ed[b].push_back(++cnt); w[cnt]=0; to[cnt]=a; } bool bfs() { memset(d,0x3f,sizeof(d)); queue<int> q; d[0]=0; q.push(0); while (!q.empty()) { int x=q.front(); q.pop(); //cout<<x<<endl; for (ri i=0;i<ed[x].size();i++) { int e=ed[x][i]; if (!w[e]) continue; if (d[x]+1<d[to[e]]) { d[to[e]]=d[x]+1; q.push(to[e]); } } } return d[n+m+1]<=N; } int dfs(int x,int limit) { if (!limit || x==n+m+1) return limit; int tot=0; for (ri &i=cur[x];i<ed[x].size();i++) { int e=ed[x][i]; if (w[e] && d[to[e]]==d[x]+1) { int f=dfs(to[e],min(limit,w[e])); if (!f) continue; w[e]-=f; w[1^e]+=f; tot+=f; limit-=f; if (!limit) return tot; } } return tot; } int solve() { int ret=0; while (bfs()) { memset(cur,0,sizeof(cur)); ret+=dfs(0,INF); } return ret; } } zyx; int main() { int u,v; scanf("%d %d",&n,&m); zyx.init(); while (1) { scanf("%d %d",&u,&v); if (u==-1 && v==-1) break; zyx.add_edge(u,v,1); } for (ri i=1;i<=n;i++) zyx.add_edge(0,i,1); for (ri i=n+1;i<=n+m;i++) zyx.add_edge(i,n+m+1,1); printf("%d ",zyx.solve()); for (ri i=0;i<=zyx.cnt;i+=2) { if (!zyx.w[i] && zyx.to[i]<=n+m && zyx.to[i]>=n+1) printf("%d %d ",zyx.to[i^1],zyx.to[i]); } return 0; }