JSOI2008 会议安排

【题目描述】

在高层峰会期间，还安排了许多专题对口重要会议：一个重要的会议将会由A国的M位代表和B国的N位代表参加 (M,N不大于1000，代表用1,2,…,M和1,2,…,N表示)。他们被预先分成K组进行商谈。每组两个人分别来自A国和B国。每个参加会议的代表都至少参加了一组谈判。会议为每一个代表都准备了一个房间。技术人员将会在一些房间之间连上直通电话，一个代表至少要和他的一个谈判对手直接联络。连接一个直通电话的价格是常数。技术人员要用尽量少的花费满足会议的要求。

【输入文件】

第一行是三个用空格隔开的整数M, N和K。下面的K行每行有一对数P1–P2，P1表示A国的代表，P2表示B国的代表。P1和P2之间用空格隔开。

【输出文件】

只有一行，即最少要装的电话的数目。

【输入样例】

3 2 4

1 1

2 1

3 1

3 2

【输出样例】

3

 

【题目分析】

还是水的不行……

把题目抽象出来，就是在一个二分图中，左边m个点，右边n个点，中间k条边，问最少用几条边覆盖所有的点。

我们尽量每次用一条边覆盖图的两边没有被覆盖的点，然后剩下的点每个点都需要一条额外的边来覆盖，这样就想到了……最大匹配

设最大匹配为P，那么ans=m+n-2*P+P=m+n-P

 

【代码实现】

1 program tyvj1816;  2 type bian=record  3       y,next:longint;  4      end;  5 var b:array[0..1000000]of bian;  6     g,f:array[0..1000]of longint;  7     v:array[0..1000]of boolean;  8     n,m,i,j,k,tot,x,y,ans:longint;  9 function dfs(s:longint):boolean; 10 var i:longint; 11 begin 12     i:=g[s]; 13     while i<>0 do 14     begin 15         if not v[b[i].y] then 16         begin 17             v[b[i].y]:=true; 18             if (f[b[i].y]=0)or dfs(f[b[i].y]) then 19             begin 20                 f[b[i].y]:=s; 21                 exit(true); 22             end; 23         end; 24         i:=b[i].next; 25     end; 26     exit(false); 27 end; 28 procedure insert(x,y:longint); 29 begin 30     inc(tot); 31     b[tot].y:=y; 32     b[tot].next:=g[x]; 33     g[x]:=tot; 34 end; 35 begin 36     readln(m,n,k); 37     for i:=1 to k do 38     begin 39         readln(x,y); 40         insert(x,y); 41     end; 42     for i:=1 to m do 43     begin 44         fillchar(v,sizeof(v),0); 45         if dfs(i) then inc(ans); 46     end; 47     ans:=m+n-ans*2+ans; 48     writeln(ans); 49 end.