1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
| #include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#define N 2505
#define M 5005
#define INF 0x3f3f3f3f
struct edge {int v,c,f,w;} edges[M<<1];
int head[N],nxt[M<<1],idx=0;
inline void clear() {idx=0;memset(head,-1,sizeof(head));}
inline void addEdge(int u,int v,int c,int w) {
edges[idx]=(edge){v,c,0,w};nxt[idx]=head[u];head[u]=idx++;
edges[idx]=(edge){u,0,0,-w};nxt[idx]=head[v];head[v]=idx++;
}
int d[N],inq[N],a[N],pa[N];
inline bool SPFA(int s,int t,int &cost) {
memset(d,0x3f,sizeof(d));d[s]=0;inq[s]=true;
std::queue<int> q;q.push(s);a[s]=INF;pa[s]=0;
while(q.size()) {
int x=q.front();q.pop();inq[x]=false;
for(register int i=head[x];~i;i=nxt[i]) {
edge &e=edges[i];
if(e.c>e.f&&d[e.v]>d[x]+e.w) {
d[e.v]=d[x]+e.w;pa[e.v]=i;
a[e.v]=std::min(a[x],e.c-e.f);
if(!inq[e.v]) {q.push(e.v);inq[e.v]=true;}
}
}
}
if(d[t]==INF) return false;
int u=t;cost+=a[t]*d[t];
while(true) {
edges[pa[u]].f+=a[t];
edges[pa[u]^1].f-=a[t];
if(u==s) break;u=edges[pa[u]^1].v;
}
return true;
}
inline int solve(int s,int t) {
int ans=0;
while(SPFA(s,t,ans));
return -ans;
}
int n,p,q;
void dfs(int x,int rt) {
for(register int i=head[x];~i;i=nxt[i]) {
edge &e=edges[i];
if(e.f>0) {
if(e.v<x) printf("%d %d\n",rt,(e.v==x-q*p+1)?1:0);
--e.f;dfs(e.v,rt);break;
}
}
}
int main() {
scanf("%d%d%d",&n,&p,&q);clear();
for(register int i=1;i<=q;++i) {
for(register int j=1;j<=p;++j) {
int state;scanf("%d",&state);
if(state==0) {
addEdge(1+(i-1)*p+j,1+q*p+(i-1)*p+j,INF,0);
}
else if(state==2) {
addEdge(1+(i-1)*p+j,1+q*p+(i-1)*p+j,1,-1);
addEdge(1+(i-1)*p+j,1+q*p+(i-1)*p+j,INF,0);
}
if(i!=q) addEdge(1+q*p+(i-1)*p+j,1+i*p+j,INF,0);
if(j!=p) addEdge(1+q*p+(i-1)*p+j,1+(i-1)*p+j+1,INF,0);
}
}
addEdge(1,2,n,0);addEdge(1+(p*q*2),1+(p*q*2)+1,n,0);
solve(1,1+(q*p*2)+1);for(register int i=1;i<=n;++i) dfs(1,i);
return 0;
}
|