hdu1507二分匹配

  
  1 //hdu1507 挺不错的题
  2 #include<stdio.h>
  3 #include<string.h>
  4 #define INF 99999999
  5 struct node
  6 {
  7     int x;
  8     int y;
  9 }rem[23005];
 10 struct Node
 11 {
 12     int v;
 13     int next;
 14 }edge[23000];
 15 int n,m,num,vis[13000],match[13300],map[130][130],mmark[13300],index,pre[10030];
 16 void add(int x,int y)
 17 {
 18     edge[index].v=y;
 19     edge[index].next=pre[x];
 20     pre[x]=index++;
 21 }
 22 void build(int x,int y,int a,int b)
 23 {
 24     int i,j;
 25     if(a<=0||a>n||b<=0||b>m||map[a][b]==0)
 26         return ;
 27     else add(map[x][y],map[a][b]);
 28 }
 29 void test(int x,int y)
 30 {
 31     build(x,y,x-1,y);
 32     build(x,y,x+1,y);
 33     build(x,y,x,y-1);
 34     build(x,y,x,y+1);
 35 }
 36 void makemap()
 37 {
 38     int i,j;
 39     for(i=1;i<=n;i++)
 40         for(j=1;j<=m;j++)
 41         {
 42             if(map[i][j]==0)
 43                 continue;
 44             test(i,j);
 45         }
 46 }
 47 int dfs(int u)
 48 {
 49     int i,j;
 50     for(i=pre[u];i!=-1;i=edge[i].next)
 51     {
 52         int j=edge[i].v;
 53         if(!vis[j])
 54         {
 55             vis[j]=1;
 56             if(match[j]==-1||dfs(match[j]))
 57             {
 58                 match[j]=u;
 59                 return 1;
 60             }
 61         }
 62     }
 63     return 0;
 64 }
 65 int main()
 66 {
 67     int i,j,k;
 68     while(scanf("%d%d",&n,&m)!=EOF)
 69     {
 70         if(!n&&!m)break;
 71         scanf("%d",&k);
 72         memset(mmark,0,sizeof(mmark));
 73         for(i=1;i<=n;i++)
 74             for(j=1;j<=m;j++)
 75                 map[i][j]=INF;
 76 
 77         for(i=0;i<k;i++)
 78         {
 79             int x,y;
 80             scanf("%d%d",&x,&y);
 81             map[x][y]=0;
 82         }
 83 
 84         num=1;
 85         for(i=1;i<=n;i++)
 86             for(j=1;j<=m;j++)
 87             {
 88                 if(map[i][j])
 89                 {
 90                     map[i][j]=num;
 91                     rem[num].x=i;
 92                     rem[num++].y=j;
 93                 }
 94             }
 95         /*for(i=1;i<=n;i++)
 96         {
 97             for(j=1;j<=m;j++)
 98                 printf("%d ",map[i][j]);
 99             printf("
");
100         }*/
101         index=1;
102         memset(pre,-1,sizeof(pre));
103         makemap();
104         /*for(i=1;i<num;i++)
105         {
106             for(j=1;j<num;j++)
107             {
108                 printf("%d ",g[i][j]);
109             }
110             printf("
");
111         }*/
112         memset(match,-1,sizeof(match));
113         int ans=0;
114         for(i=1;i<num;i++)
115         {
116             memset(vis,0,sizeof(vis));
117             if(dfs(i))
118                 ans++;
119         }
120         int mark[1300];
121         memset(mark,0,sizeof(mark));
122         printf("%d
",ans/2);
123         for(i=1;i<num;i++)
124         {
125             if(!mark[i]&&!mark[match[i]]&&match[i]!=-1)
126             {
127                 printf("(%d,%d)--(%d,%d)
",rem[i].x,rem[i].y,rem[match[i]].x,rem[match[i]].y);
128                 mark[i]=1;mark[match[i]]=1;
129             }
130         }
131         printf("
");
132     }
133 }
134 
135 
136 /*
137 
138 3 3
139 4
140 2 3
141 1 3
142 3 2
143 1 2
144 4 5
145 6
146 1 2
147 1 3
148 3 5
149 3 4
150 4 2
151 2 5
152 
153 */