题意：给你n个幻灯片，每个幻灯片有个数字编号1~n,现在给每个幻灯片用A~Z进行编号，那么问有多少个幻灯片的数字和字母是唯一对应的
二分图的完全匹配的必须边，裸的。
这道题目可以用
http://www.cnblogs.com/proverbs/archive/2012/08/29/2662638.html
方法来解。。但是我的第一反应就是删边。于是乎，用删边的方法做的
先做一遍匹配，匈牙利。然后对于匹配中的每条边都删除一遍，如果不能达到完全匹配，则这条边是必须边。
大致思想就是这样了
代码里几个我犯错的地方写了注释
View Code
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cstring> 4 #define N 40 5 #define M 1600 6 using namespace std; 7 int n,x1[N],x2[N],y1[N],y2[N],x,y,head[N],next[M],to[M],bh[N][N],ban,cnt,linky[N],first_ans,cas; 8 bool vis[N]; 9 void add(int u,int v) 10 { 11 to[cnt]=v; next[cnt]=head[u]; head[u]=cnt++; 12 } 13 void read() 14 { 15 memset(head,-1,sizeof head);cnt=0; 16 for(int i=1;i<=n;i++) scanf("%d%d%d%d",&x1[i],&x2[i],&y1[i],&y2[i]); 17 for(int i=1;i<=n;i++) 18 { 19 scanf("%d%d",&x,&y); 20 for(int j=1;j<=n;j++) 21 if(x>x1[j]&&x<x2[j]&&y>y1[j]&&y<y2[j]) 22 { 23 bh[i][j]=cnt;//两点连线的编号 24 add(i,j); 25 } 26 } 27 } 28 bool dfs(int u) 29 { 30 for(int i=head[u];~i;i=next[i]) 31 if(!vis[to[i]]&&ban!=i) 32 { 33 vis[to[i]]=true; 34 if(linky[to[i]]==-1||dfs(linky[to[i]])) 35 { 36 linky[to[i]]=u; 37 return true; 38 } 39 } 40 return false; 41 } 42 void first_match() 43 { 44 memset(linky,-1,sizeof linky); 45 for(int i=1;i<=n;i++) 46 { 47 memset(vis,0,sizeof vis); 48 if(dfs(i)) first_ans++; 49 } 50 } 51 void go() 52 { 53 ban=-1; 54 first_match(); 55 bool bj=false; 56 printf("Heap %d\n",cas); 57 for(int i=1,tmp;i<=n;i++) 58 { 59 tmp=linky[i]; 60 ban=bh[tmp][i];//ban是删的边，注意tmp是左边的点，i是右边的点 61 linky[i]=-1; 62 memset(vis,0,sizeof vis); 63 if(!dfs(tmp)) 64 { 65 bj=true,printf("(%c,%d) ",'A'+i-1,tmp); 66 linky[i]=tmp;//必须放在括号内，因为如果dfs返回true的话说明有新的匹配，linky不能更新 67 } 68 } 69 if(bj) printf("\n\n"); 70 else printf("none\n\n"); 71 } 72 int main() 73 { 74 while(scanf("%d",&n),n) 75 { 76 cas++; 77 read(); 78 go(); 79 } 80 return 0; 81 }
话说，我这个蒟蒻POJ终于到了300题了。。
还是太弱，XLk神牛每天40题呢。。
OTZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ