1.
#include<iostream> #include<cstdio> #include<cstring> #define N 202 using namespace std; int Li[N],vis[N],con[N][N]; int n,m,ans,f,x; bool dfs(int x) { for(int i=1;i<=m;i++) { if(con[x][i] && !vis[i]) { vis[i]=1; if(!Li[i] || dfs(Li[i])) { Li[i]=x; return true; } } } return false; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&f); for(int j=1;j<=f;j++) { scanf("%d",&x); con[i][x]=1; } } for(int i=1;i<=n;i++) { memset(vis,0,sizeof vis); if(dfs(i)) ans++; } printf("%d ",ans); return 0; }
2.
/* 开始把边取反，然后跑一边匈牙利算法，然后判断是不是完美匹配（概念网上自己去找），不是就直接输出none； 第二步每次删掉一条边，判断是不是完美匹配，不是就输出这个两个点； 第二步跑完之后没有发现有一个是可以输出的，就输出none； */ #include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #define N 555 using namespace std; int mx[N],Li[N],head[N]; int n,cut_x,cut_y,S[N],T[N],num,flag=0; bool vis[N],k[N][N]; struct node { int u; int to; int next; } e[N<<1]; void add(int u,int to) { e[++num].to=to;e[num].next=head[u];head[u]=num; } int dfs(int x) { int v; for (int i=head[x];i!=0;i=e[i].next) { v=e[i].to; if(x==cut_x && v==cut_y) continue; if(vis[v]==true) continue; vis[v]=true; if(Li[v]==0 || dfs(Li[v]) ) { mx[x]=v; Li[v]=x; return 1; } } return 0; } int maxmatch() { int ans=0; for (int i=1;i<=n;i++) { for (int j=1;j<=n;j++) vis[j]=false; ans+=dfs(i); } return ans; } void Impotant_edge() { int ans; for (int i=1;i<=n;i++) { S[i]=i;T[i]=mx[i]; } for (int i=1;i<=n;i++) { cut_x=S[i];cut_y=T[i]; for (int j=1;j<=n;j++) mx[j]=0,Li[j]=0; ans=maxmatch(); if (ans!=n) { printf("%d %d ",cut_x,cut_y); flag=1; } } return; } int main() { int ans,x,y; scanf("%d",&n); while(1) { scanf("%d%d",&x,&y); if (x==0&&y==0) break; k[x][y]=1; } for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) if( k[i][j]==0 ) add(i,j); ans=maxmatch(); if (ans!=n) { cout<<"none"<<endl; return 0; } else { Impotant_edge(); if (flag==0) cout<<"none"<<endl; return 0; } }
3
/* 这道题显然是求最长反链, 最长反链=最小链覆盖.最小链覆盖就是先做一次floyd传递闭包, 再求最小路径覆盖. 最小路径覆盖=N - 二分图最大匹配. 所以把所有点拆成x,y两个, 然后存在edge(u,v)就连ux->vy. 然后跑匈牙利即可. */ #include<iostream> #include<cstdio> #include<cstring> #define N 207 using namespace std; int n,m,ans,x,y; int f[N][N],Li[N],a[N][N]; bool vis[N]; void floyd() { for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) f[i][j]|=f[i][k]&f[k][j]; } bool dfs(int x) { for(int i=1;i<=n;i++) { if(f[x][i] && !vis[i]) { vis[i]=true; if(!Li[i] || dfs(Li[i])) { Li[i]=x; return true; } } } return false; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); f[x][y]=1; } floyd(); for(int i=1;i<=n;i++) { memset(vis,0,sizeof vis); if(dfs(i)) ans++; } printf("%d ",n-ans); return 0; return 0; return 0; }
4.
/* 二分图输出方案 */ #include<iostream> #include<cstdio> #include<cstring> #define MAX 200 #define MAXL 200*200 using namespace std; struct Line { int v,next; } e[MAXL]; int head[MAX],Li[MAX]; int n,m,u,v,sum,cnt; bool vis[MAX]; inline void Add(int u,int v) { e[++cnt].v=v;e[cnt].next=head[u];head[u]=cnt; } bool dfs(int u) { for(int i=head[u]; i!=-1; i=e[i].next) { int v=e[i].v; if(!vis[v]) { vis[v]=true; if(!Li[v]||dfs(Li[v])) { Li[v]=u; return true; } } } return false; } int main() { memset(head,-1,sizeof(head)); scanf("%d%d",&n,&m); while(1) { scanf("%d%d",&u,&v); if(u==-1)break; Add(u,v); } for(int i=1; i<=n; ++i) { memset(vis,0,sizeof(vis)); if(dfs(i)) ++sum; } printf("%d ",sum); for(int i=n+1; i<=m; ++i) if(Li[i]) printf("%d %d ",Li[i],i); return 0; return 0; return 0; }
5.
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int n,m,q[5001][5001],d[5001],g[5001],sum; int map[5001][5001],march[5001],flag[5001],xv[5001]; int dfs(int v) { for(int i=1; i<=n; i++) { if(map[v][i]==1&&flag[i]==0) { flag[i]=1; if(march[i]==0||dfs(march[i])) { march[i]=v; return 1; } } } return 0; } int main() { cin>>n; int t; for(int i=1; i<=n; i++) { cin>>g[i]; for(int j=1; j<=g[i]; j++) cin>>q[i][j]; } cin>>m; for(int i=1; i<=m; i++) { cin>>xv[i]; for(int j=1; j<=n; j++) { for(int k=1; k<=g[j]; k++) { if(q[j][k]==xv[i])map[xv[i]][j]=1; } } } for(int i=1; i<=m; i++) { memset(flag,0,sizeof(flag)); if(dfs(xv[i]))sum++; } cout<<sum; return 0; }
6.
/* 其实很简单，做两个二分图即可。 可以构造两个二分图，依次从某一个客人出发同时对两个二分图寻找增广路 若对某一个二分图没有找到增广路，则恢复从该客人出发找到的所有增广路(这条不行)， 反之，则改进匹配。 */ #include<iostream> #include<cstdio> #include<cstring> #define N 101 using namespace std; int n,p,q,i,j,RL[N][N],FL[N][N],LB[N],book[N],answer,eat[N]; bool CR[N],visR[N],visF[N],LCR[N],CF[N]; bool room_(int No) { for (int i=1; i<=n; i++) if (RL[No][i]&&!visR[i]) { visR[i]=1; if (book[i]==0||room_(book[i])) { CR[No]=1; book[i]=No; return 1; } } return 0; } bool food_(int No) { for (int i=1; i<=n; i++) if (FL[No][i]&&!visF[i]) { visF[i]=1; if (eat[i]==0||food_(eat[i])) { CF[No]=1; eat[i]=No; return 1; } } return 0; } int main () { scanf("%d%d%d",&n,&p,&q); for (i=1; i<=n; i++) for (j=1; j<=p; j++) scanf("%d",&RL[i][j]); for (i=1; i<=n; i++) for (j=1; j<=q; j++) scanf("%d",&FL[i][j]); while (1) { for (i=1; i<=n; i++) if (!CR[i]) { for (j=1; j<=n; j++) visR[j]=0; for (j=1; j<=n; j++) visF[j]=0; for (j=1; j<=n; j++) LCR[j]=CR[j]; for (j=1; j<=n; j++) LB[j]=book[j]; if (room_(i)&&food_(i)) { answer++; continue; } else//因为无法匹配所以取消上次所有增广 { for (j=1; j<=n; j++) CR[j]=LCR[j]; for (j=1; j<=n; j++) book[j]=LB[j]; } } break; } printf("%d ",answer); return 0; return 0; return 0; }