题目链接：https://www.oj.swust.edu.cn/problem/show/1736
就是求最大匹配，用匈牙利算法就可以了。
如果不会匈牙利算法 推荐博客：https://www.cnblogs.com/PencilWang/p/5769385.html
用匈牙利算法的代码：
#include<iostream> #include<cstring> #include<algorithm> #include<queue> #include<map> #include<stack> #include<cmath> #include<vector> #include<set> #include<cstdio> #include<string> #include<deque> using namespace std; typedef long long LL; #define eps 1e-8 #define INF 0x3f3f3f3f #define maxn 105 /*struct point{ int u,w; }; bool operator <(const point &s1,const point &s2) { if(s1.w!=s2.w) return s1.w>s2.w; else return s1.u>s2.u; }*/ int pre[maxn],vis[maxn],head[maxn]; int n,m,k,t,cnt,ans; struct node{ int v,next; }edge[maxn*maxn]; void init() { fill(head,head+maxn-1,-1); fill(pre,pre+maxn-1,-1); cnt=ans=0; } void add(int u,int v) { edge[++cnt].v=v; edge[cnt].next=head[u]; head[u]=cnt; } bool hungry(int u) { for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if(vis[v]) continue; vis[v]=1; if(pre[v]==-1||hungry(pre[v])) { pre[v]=u; return true; } } return false; } int main() { while(scanf("%d%d",&m,&n)!=EOF) { init(); int u,v; while(scanf("%d%d",&u,&v)&&(u!=-1&&v!=-1)) { add(v,u); } for(int i=m+1;i<=n;i++) { fill(vis,vis+maxn-1,0); if(hungry(i)) ans++; } printf("%d ",ans); for(int i=1;i<=m;i++) { if(pre[i]!=-1) printf("%d %d ",i,pre[i]); } } return 0; }
也要用最大流写一下：
不会最大流的话：推荐博客：https://blog.csdn.net/x_y_q_/article/details/51999466
#include<iostream> #include<cstring> #include<algorithm> #include<queue> #include<map> #include<stack> #include<cmath> #include<vector> #include<set> #include<cstdio> #include<string> #include<deque> using namespace std; typedef long long LL; #define eps 1e-8 #define INF 0x3f3f3f #define maxn 105 /*struct point{ int u,w; }; bool operator <(const point &s1,const point &s2) { if(s1.w!=s2.w) return s1.w>s2.w; else return s1.u>s2.u; }*/ queue<int>q; int capacity[maxn][maxn],depth[maxn];//数组capacity记录弧的容量 int n,m,k,t; int BFS(int src,int des)//BFS分层 { while(!q.empty()) q.pop(); memset(depth,-1,sizeof(depth)); depth[src]=0; q.push(src); while(!q.empty()) { int u=q.front(); q.pop(); for(int i=1;i<=n+1;i++) { if(depth[i]==-1&&capacity[u][i]>0) { depth[i]=depth[u]+1; q.push(i); } } } return depth[des]!=-1; } int DFS(int u,int min1)//DFS不断找增广路 { if(u==n+1) return min1; for(int i=1;i<=n+1;i++) { if(depth[i]==depth[u]+1&&capacity[u][i]>0) { int increase=DFS(i,min(min1,capacity[u][i])); if(increase>0) { capacity[u][i]-=increase; capacity[i][u]+=increase; return increase; } } } return -1; } int maxflow(int src,int des) { int sumflow=0,increase=0; while(BFS(src,des)) { while((increase=DFS(src,INF))>0) { sumflow+=increase; } } return sumflow; } int main() { while(scanf("%d%d",&m,&n)!=EOF) { memset(capacity,0,sizeof(capacity)); int u,v; while(scanf("%d%d",&u,&v)&&u!=-1&&v!=-1) { capacity[u][v]+=1; } for(int i=1;i<=m;i++)//添加点0作为源点，并且点1到点m这些点与点0的容量为1 capacity[0][i]+=1; for(int i=m+1;i<=n;i++)//添加点n+1作为汇点，。。。 capacity[i][n+1]+=1; printf("%d ",maxflow(0,n+1)); for(int i=1;i<=m;i++)//这里因为要输出两两组合的数字，所以我们可以看哪些弧增加了反向边 { for(int j=m+1;j<=n;j++) { if(capacity[j][i]>0)//i与j之间增加了一条反向边 printf("%d %d ",i,j); } } } return 0; }