10.31T1 二分图

1.列队

(phalanx)

【问题描述】

Sylvia是一个热爱学习的女孩子。
在平时的练习中，他总是能考到std以上的成绩，前段时间，他参加了一场练习赛，众所周知，机房是一个方阵。这天，他又打爆了std，感到十分无聊，便想要hack机房内同学的程序，他会挑选一整行或一整列的同学进行hack ( 而且每行每列只会hack一次 )，然而有些同学不是那么好惹，如果你hack了他两次，他会私下寻求解决,Sylvia十分害怕，只会hack他们一次。假设Sylvia的水平十分高超，每次hack都能成功，求他最多能hack多少人次？

【输入】

第一行两个数表示机房的大小和不好惹的同学个数
接下来x行，每行两个数表示不好惹的同学坐标

【输出】

一个数表示最多hack多少次

【样例输入】

2 1

1 1

【样例输入】

样例说明

他可以hack第一行、第二行、第二列一共6次

【数据范围与约定】

对于20%的数据 n<=10, x<=100
对于40%的数据 n<=20 , x<=400
对于100%的数据 n<=1000 , x<=4000，1<=x,y<=n且同一个点不会重复出现

一个简单的二分图，同学的行和列只能选一个显然就是二分图模型，直接往上面套就可以了

code：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 int g[3000][3000];
 6 int n,m;
 7 int vis[3000],matching[3000];
 8 bool match(int u) {
 9     for(int i =1; i<=n; i++) {
10         if(vis[i]||!g[u][i])continue;
11         vis[i]=1;
12         if(!matching[i]||match(matching[i])) {
13             matching[i]=u;
14             return true;
15         }
16     }
17     return false;
18 }
19 int hun() {
20     int ans=0;
21     for(int i=1; i<=n; i++) {
22         memset(vis,0,sizeof vis);
23         if(match(i))ans++;
24     }
25     return ans;
26 }
27 int read(){
28     int x=0,f=1;
29     char c=getchar();
30     while(!isdigit(c)){
31         if(c=='-')f=-1;
32         c=getchar();
33     }
34     while(isdigit(c)){
35         x=(x<<3)+(x<<1)+c-'0';
36         c=getchar();
37     }
38     return x*f;
39 }
40 int main() {
41     freopen("phalanx.in","r",stdin);
42     freopen("phalanx.out","w",stdout);
43     n=read(),m=read();
44     for(int i=1; i<=m; i++) {
45         int a,b;
46         a=read(),b=read();
47         g[a][b]=1;
48     }
49     cout<<(2*n-hun())*n;
50     return 0;
51 }

over