分析:先建边，这里可以直接标记那些边不能跑，然后直接aug的时候暴力枚举所有点，然后跑出来如果不是完美匹配肯定是none，否则的话，我们对于每一条已经连的边，断开来，看是否是完美匹配必须需要的边，如果是的话就输出。
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) using namespace std; int n,m; const int N=1e5+5; int boy[N],girl[N],del[2005][2005]; bool vis[2005]; inline bool find(int x) { fo(i,1,n) if (!vis[i]&&!del[x][i]) { vis[i]=1; if(!girl[i]||find(girl[i])) { girl[i]=x; boy[x]=i; return 1; } } return 0; } int main() { scanf("%d",&n); int x,y; while (scanf("%d%d",&x,&y)&&x&&y) del[x][y]=1; int ans=0; fo(i,1,n) { memset(vis,0,sizeof(vis)); if (find(i))++ans; } if (ans!=n) { printf("none\n"); return 0; } bool flag=0; fo(i,1,n) { memset(vis,0,sizeof(vis)); int j=boy[i]; del[i][j]=1; girl[j]=0,boy[i]=0; if (!find(i)) { printf("%d %d\n",i,j); boy[i]=j,girl[j]=i,flag=1; } del[i][j]=0; } if (!flag)printf("none\n"); return 0; }