1.列队
(phalanx)
【问题描述】
Sylvia是一个热爱学习的女孩子。
在平时的练习中，他总是能考到std以上的成绩，前段时间，他参加了一场练习赛，众所周知，机房是一个方阵。这天，他又打爆了std，感到十分无聊，便想要hack机房内同学的程序，他会挑选一整行或一整列的同学进行hack ( 而且每行每列只会hack一次 )，然而有些同学不是那么好惹，如果你hack了他两次，他会私下寻求解决,Sylvia十分害怕，只会hack他们一次。假设Sylvia的水平十分高超，每次hack都能成功，求他最 多能hack多少人次？【输入】
第一行两个数 表示机房的大小和不好惹的同学个数
接下来x行，每行两个数 表示不好惹的同学坐标【输出】
一个数表示最多hack多少次
【样例输入】
2 1
1 1
【样例输入】
6
样例说明
他可以hack第一行、第二行、第二列一共6次
【数据范围与约定】
对于20%的数据 n<=10, x<=100
对于40%的数据 n<=20 , x<=400 对于100%的数据 n<=1000 , x<=4000，1<=x,y<=n且同一个点不会重复出现
一个简单的二分图，同学的行和列只能选一个显然就是二分图模型，直接往上面套就可以了
code：
1 #include2 #include 3 #include 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