洛谷P2071 座位安排 （二分图匹配） HQG

座位安排 （二分图匹配） HQG"/>

洛谷P2071 座位安排 （二分图匹配） HQG

传送门

算法：二分图匹配（很明显的）

思路：把每一排的两个位置拆开（及成为了2*N排位置），把i可选的a和b建成4条边。

之后2N个人去匹配2N个作为（这就是很裸的二分图匹配了），在这里就不说了。（不会的点着）

CODE：

#include <bits/stdc++.h>
using namespace std;
const int N = 4000 + 10 ;
struct node{int v,next ;
}e[10*N];
int use[N],head[N],result[N] ;
int n,m,a,b,t,tot,ans=0 ;
void add_edge(int a,int b){e[tot].v=b ;e[tot].next=head[a] ;head[a]=tot++ ;
}
bool dfs(int now){for (int i=head[now];i;i=e[i].next) {int to=e[i].v ;if (use[to]!=t){ use[to]=t ;if (!result[to] || dfs(result[to])){ //没有匹配过 或 匹配者可以调配 result[to]=now ;return true ; } } }return false ;
}
void hungarian() {for (int i=1;i<=n;i++){t=i ;if (dfs(i)) ans++ ;}printf("%d\n",ans) ;return ;
}
int main(){scanf("%d",&n) ;for (int i=1;i<=2*n;i++) {scanf("%d %d",&a,&b) ;add_edge(i,a) ;add_edge(i,a+n) ;add_edge(i,b) ;add_edge(i,b+n) ;}n*=2 ;hungarian() ;return 0 ; 
}