URAL 1721. Two Sides of the Same Coin 二分匹配构图

1721. Two Sides of the Same Coin

Time limit: 1.0 secondMemory limit: 64 MB

That was a good question. The contest rules state that every problem should be prepared by two persons exactly: one should write a statement, the other one should prepare a set of tests. Generally, professional problemsetters have license for only one of the tasks, but some of them can do both. Besides, to eliminate a possibility of conflicts between the problemsetters working on the same problem, the difference of their ranks should be equal to 2.

Input

The first line contains the numbernof problemsetters in the program committee (2 ≤n≤ 1000). Each of the followingnlines contains a problemsetter’s name, his specialization and his rank separated with spaces. The name consists of up to 20 Latin letters. There are no two problemsetters with the same name. Specialization is denoted by one of the three words: “statements”, “testdata”, or “anything”, corresponding to the people able to write statements, people able to prepare the tests and to the people able to do both. The rank is an integer in range from 3 to 1000.

Output

In the first line output the maximal number of problems that can be prepared for the contest. For each of these problems output a line containing the name of a person writing the statement, a space, and the name of a person preparing the tests. If there are several ways to prepare such an amount of problems output any one.

Sample

inputoutput

7Poll anything 8Tejat statements 6Mebsuta testdata 6Propus testdata4Alzir anything 7Mekbuda anything 3Dirah testdata 93Poll MebsutaTejat PropusAlzir Dirah

题目很长，没有全部复制过来，贴了重要的那一段。

题意：有n个人，每个人各自会statements 或者testdata ，或者两种都会anything 。后面还有一个数字rank。

然后找最大匹配，要求，必须有个人会statements 有个人会testdata。然后rank的差要正好是2。

做法：因为rank差要2。如 0 1 |2 3 | 4 5| 6 7，如果两个数两个数直接隔开当作一个格的话，可以发现只有奇数格和偶数格才有可能会匹配。所以可以把rank%4，如果等于0 1，放一侧，如果等于 2，3 放另一侧。然后计算最大匹配。

注意：会statements 的输出在左，另一个输出在右。

失败的案例：一开始就想到了二分匹配，用最大流来构图做的。当时想的是把所有人左边放一排，右边放一排，然后把符合要求的连起来，，求最大匹配。因为一直找不到错误案例，所以WA了很多次。

总结：二分匹配，如果给的数据不是对立的两堆，而是一堆的话。要想方法把这一堆分成两堆，两堆各自之中一定没有可以相互匹配的。

构图失败的：

#pragma warning (disable:4786)#include <stdio.h>#include <stdlib.h>#include <string.h>#include <limits.h>#include <malloc.h>#include <ctype.h>#include <math.h>#include <string>#include <iostream>#include <algorithm>using namespace std;#include <stack>#include <queue>#include <vector>#include <deque>#include <set>#include <map> const int MAXN = 22222;//点数的最大值const int MAXM = 9000000;//边数的最大值const int INF = 2000000000;struct Edge{int to,next,cap,flow;}edge[MAXM];//注意是MAXMint tol;int head[MAXN];int gap[MAXN],dep[MAXN],cur[MAXN];void init(){tol = 0;memset(head,-1,sizeof (head));}void addedge (int u,int v,int w,int rw = 0)//网络流要有反向弧{edge[tol].to = v; edge[tol].cap = w; edge[tol].flow = 0;edge[tol].next = head[u]; head[u] = tol++;edge[tol].to = u; edge[tol].cap = rw; edge[tol].flow = 0;edge[tol].next = head[v]; head[v] = tol++;}int Q[MAXN];void BFS(int start,int end){memset(dep,-1,sizeof(dep));memset(gap,0,sizeof(gap));gap[0] = 1;int front = 0, rear = 0;dep[end] = 0;Q[rear++] = end;while(front != rear){int u = Q[front++];for(int i = head[u]; i != -1; i = edge[i].next){int v = edge[i]. to;if(dep[v] != -1)continue;Q[rear++] = v;dep[v] = dep[u] + 1;gap[dep[v]]++;}}}int S[MAXN];int sap(int start,int end, int N)//有几个点{BFS(start,end);memcpy(cur,head,sizeof(head)); int top = 0;int u = start;int ans = 0;int i;while(dep[start] < N){if(u == end){int Min = INF;int inser;for( i = 0;i < top;i++){if(Min > edge[S[i]].cap – edge[S[i]].flow){Min = edge[S[i]].cap – edge[S[i]].flow;inser = i;}}for( i = 0;i < top;i++){edge[S[i]]. flow += Min;edge[S[i]^1].flow -= Min;}ans += Min;top = inser;u = edge[S[top]^1].to;continue;}bool flag = false;int v;for( i = cur[u]; i != -1; i = edge[i]. next){v = edge[i]. to;if(edge[i].cap – edge[i].flow && dep[v]+1 == dep[u]){flag = true;cur[u] = i;break;}}if(flag){S[top++] = cur[u];u = v;continue;}int Min = N;for( i = head[u]; i != -1; i = edge[i].next){if(edge[i].cap – edge[i].flow && dep[edge[i].to] < Min){Min = dep[edge[i].to];cur[u] = i;}}gap[dep[u]]–;if(!gap[dep[u]]) return ans;dep[u] = Min + 1;gap[dep[u]]++;if(u != start)u = edge[S[–top]^1].to;}return ans;} /*int main(){int n,m,a,b,c;while(scanf("%d%d",&n,&m)!=EOF){init();for(int i=1;i<=n;i++){scanf("%d%d%d",&a,&b,&c);addedge(a,b,c,0);}printf("%d\n",sap(1,m,m));}return 0;}*/int sta[1010];string name[1010];int rak[1010];int main(){int n;while(scanf("%d",&n)!=EOF) // 0-2n-1 是点左边i*2 右边2*i+1 ss=2*n ee=2*n+1{ init();int ss=2*n,ee=2*n+1;for(int i=0;i<n;i++){string status;cin>>name[i]>>status>>rak[i];if(status=="anything")sta[i]=3;else if(status=="statements")sta[i]=1;elsesta[i]=2;addedge(ss,i*2,1,0);addedge(i*2+1,ee,1,0);//2*n条边}for(int i=0;i<n;i++){for(int j=0;j<i;j++){if((sta[i]|sta[j])==3&&abs(rak[i]-rak[j])==2){addedge(j*2,i*2+1,1,0);addedge(i*2,j*2+1,1,0);//printf("%d %d\n",i,j);}}}int ans=sap(ss,ee,2*n+2);printf("%d\n",ans/2);for(int i=4*n;i<tol;i+=4){if(edge[i].flow==1){int fir=edge[i+1].to/2;int sec=edge[i].to/2;if(sta[fir]==2)swap(fir,sec);if(sta[sec]==1)swap(fir,sec);cout<<name[fir]<<' '<<name[sec]<<endl;}}}return 0;}/*2Propus testdata 4 Tejat anything 6 statementsanything testdata3Alzir DirahTejat PropusPoll Mebsuta*/

要知道，当你一直在担心错过了什么的时候，

相关文章：

你感兴趣的文章：

标签云：