lg2071 发表于 2018-03-14 | 分类于 算法 , 图论 , 二分图匹配 | 阅读数 次 链接:lg2071 Description 已知车上有N排座位,有N*2个人参加省赛,每排座位只能坐两人,且每个人都有自己想坐的排数,问最多使多少人坐到自己想坐的位置。 Input 第一行,一个正整数N。 第二行至第N*2+1行,每行两个正整数Si1,Si2,为每个人想坐的排数。Output 一个非负整数,为最多使得多少人满意。Sample Input 4 1 2 1 3 1 2 1 3 1 3 2 4 1 3 2 3Sample Output 7题解 二分图匹配,每个人加4次边就好了 mdzz 数组开大10倍,TLE无限次。。。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#include<iostream>#include<cstdio>#include<cstdlib>#include<cmath>#include<cstring>#include<algorithm>#define rep(i,x,y) for(register int i=x;i<=y;++i)#define repd(i,x,y) for(register int i=x;i>=y;--i)#define ll long longusing namespace std;const int N=1e6;struct node{ int v,nxt; inline void init(int a,int b){v=a; nxt=b;}}e[N];int head[N],cnt=1,vis[N],mark[N],n,ans;template <typename T>inline void read(T &x){ char c;int sign=1;x=0; do{c=getchar(); if(c=='-')sign=1;}while(c<'0'||c>'9'); do{x=x*10+c-'0'; c=getchar();}while(c>='0'&&c<='9'); x*=sign;}inline void reade(int a,int b){e[cnt].init(b,head[a]); head[a]=cnt++;}int find(int u){ for(int i=head[u];i;i=e[i].nxt)if(!vis[e[i].v]){ vis[e[i].v]=1; if(!mark[e[i].v]||find(mark[e[i].v])){ mark[e[i].v]=u; return 1; } } return 0;}int main(){ scanf("%d",&n); rep(i,1,n*2){ int x; scanf("%d",&x); reade(i,x); reade(i,x+n); scanf("%d",&x); reade(i,x); reade(i,n+x); } ans=0; rep(i,1,n*2){ memset(vis,0,sizeof(vis)); if(find(i))ans++; } printf("%d\n",ans); return 0;}