poj 1719 Shooting Contest (匈牙利算法)
题意：射箭比赛，靶子是一个n*m的网格。网格的特点是没列只有两个白色，剩下的全是黑色。一共射m次，每列射一次，要求每行都射到至少一次才算合法，问是否有合法射法，如果有输出一组解。
思路：由于列数可能比行数多，那么我们把行编号作为左集合，列编号作为右集合，做一次匈牙利，对于每一行都找到它匹配的列，如果匹配数等于n，说明有解。对于输出一组街的问题，m列中已经匹配了n列，输出他们对应的link即可。对于剩下的m-n列，可以任意输出。由于之前不知道会剩下哪n-m列，所以在读入的时候有必要保存每一列的white格子的位置信息。
1A,有点爽。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年05月30日 星期一 20时44分59秒
4File Name :code/poj/1719.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=1E3+7;
34int n,m;
35char maze[N][N];
36int head[2*N];
37int cnt;
38int link[2*N];
39int vis[2*N];
40pi white[N];
41struct Edge
42{
43 int v;
44 int nxt;
45}edge[N*2];
46
47void addedge( int u,int v)
48{
49 edge[cnt].v = v;
50 edge[cnt].nxt = head[u];
51 head[u] = cnt;
52 cnt++;
53}
54void init()
55{
56 cnt = 0;
57 ms(head,-1);
58
59}
60
61
62int find( int u)
63{
64 for ( int i = head[u] ; i!=-1 ; i = edge[i].nxt)
65 {
66 int v = edge[i].v;
67 if (vis[v]) continue;
68 vis[v] = true;
69 if (link[v]==-1||find(link[v]))
70 {
71 link[v] = u ;
72 return true;
73 }
74 }
75 return false;
76}
77int hungary()
78{
79 int res = 0 ;
80 ms(link,-1);
81
82 for ( int i = 1 ; i <= n ; i++)
83 {
84 ms(vis,false);
85 if (find(i)) res++;
86 }
87 // cout<<"res:"<<res<<endl;
88 return res;
89}
90int main()
91{
92 #ifndef ONLINE_JUDGE
93 freopen("code/in.txt","r",stdin);
94 #endif
95 int T;
96 cin>>T;
97 while (T--)
98 {
99 init();
100 scanf("%d%d",&n,&m);
101 int tot = 0;
102 for ( int i = 1 ; i <= m ; i++)
103 {
104 int x1,x2;
105 scanf("%d %d",&x1,&x2);
106 white[++tot]=make_pair(x1,x2);
107
108 addedge(x1,i+n);
109 addedge(x2,i+n);
110 }
111
112 int ans = hungary();
113 if (ans<n)
114 {
115 puts("NO");
116 }
117 else
118 {
119 //for ( int i = n+1 ; i <= n+m ; i++) cout<<"link[i]:"<<link[i]<<endl;
120 for ( int i = n+1 ; i <= n+m ; i++)
121 {
122 if (link[i]==-1)
123 {
124 printf("%d ",white[i-n].fst);
125 }
126 else
127 {
128 printf("%d ",link[i]);
129 }
130 }
131 printf("\n");
132 }
133
134 }
135
136 #ifndef ONLINE_JUDGE
137 fclose(stdin);
138 #endif
139 return 0;
140}