题解：
http://wenku.baidu.com/view/0ad00abec77da26925c5b01c.html
吐槽这题数据，本地测全wa，就一直对拍，最后毛了，交了一发，ac了。。。
难道这个题是spj？
View Code
1
#include <iostream>
2
#include <cstring>
3
#include <cstdio>
4
#include <cstdlib>
5
#include <algorithm>
6
#include <ctime>
7
8
#define
N 20000
9
#define
M 2001000
10
11
using
namespace
std;
12
13
int
head[N],to[M],next[M],len[M],pr[M];
14
int
pre[N],n,m,p,S,T,dis[N],q[M<<
1
],cnt;
15
int
kr[
200
][
200
],cha[N],fx[N],rd[N],num;
16
int
ts[
200
][
200
];
17
bool
vis[N];
18
double
ttt;
19
20
inline
void
add(
int
u,
int
v,
int
r,
int
w)
21
{
22
to[cnt]=v; len[cnt]=r; pr[cnt]=w; next[cnt]=head[u]; head[u]=cnt++
;
23
to[cnt]=u; len[cnt]=
0
; pr[cnt]=-w; next[cnt]=head[v]; head[v]=cnt++
;
24
}
25
26
inline
void
read()
27
{
28
scanf(
"
%d
"
,&
n);
29
memset(rd,
0
,
sizeof
rd);
30
memset(head,-
1
,
sizeof
head); cnt=
0
;
31
m=n*(n-
1
)/
2
;
32
S=
0
; T=m+n+
1
; num=
0
;
33
for
(
int
i=
1
;i<=n;i++
)
34
for
(
int
j=
1
;j<=n;j++
)
35
{
36
scanf(
"
%d
"
,&
kr[i][j]);
37
if
(j<=i)
continue
;
38
num++
;
39
if
(kr[i][j]==
2
) add(num,i+m,
1
,
0
),add(num,j+m,
1
,
0
),rd[i]++,rd[j]++
;
40
else
if
(kr[i][j]==
1
) add(num,i+m,
1
,
0
),rd[i]++
;
41
else
add(num,j+m,
1
,
0
),rd[j]++
;
42
}
43
for
(
int
i=
1
;i<=m;i++) add(S,i,
1
,
0
);
44
for
(
int
i=
1
;i<=n;i++
)
45
for
(
int
j=
1
;j<=rd[i];j++
)
46
add(i+m,T,
1
,cha[j]);
47
}
48
49
inline
bool
spfa()
50
{
51
memset(dis,
0x3f
,
sizeof
dis);
52
memset(pre,-
1
,
sizeof
pre);
53
int
h=
1
,t=
2
,sta;
54
q[
1
]=S; vis[S]=
true
; dis[S]=
0
;
55
while
(h<
t)
56
{
57
sta=q[h++]; vis[sta]=
false
;
58
for
(
int
i=head[sta];~i;i=
next[i])
59
if
(len[i]&&dis[to[i]]>dis[sta]+
pr[i])
60
{
61
dis[to[i]]=dis[sta]+
pr[i];
62
pre[to[i]]=
i;
63
if
(!vis[to[i]]) vis[to[i]]=
true
,q[t++]=
to[i];
64
}
65
}
66
return
pre[T]!=-
1
;
67
}
68
69
inline
void
updata()
70
{
71
for
(
int
i=pre[T];~i;i=pre[to[i^
1
]])
72
{
73
len[i]-=
1
; len[i^
1
]+=
1
;
74
}
75
}
76
77
inline
int
findwho(
int
u)
78
{
79
for
(
int
i=head[u];~i;i=
next[i])
80
if
(!len[i])
return
to[i];
81
}
82
83
inline
void
go()
84
{
85
int
ans=
0
;
86
while
(spfa()) ans+=
dis[T],updata();
87
printf(
"
%d\n
"
,(n*(n-
1
)*(n-
2
)/
3
+m-ans)/
2
);
88
89
int
now=
0
;
90
for
(
int
i=
1
,t;i<=n;i++
)
91
for
(
int
j=i+
1
;j<=n;j++
)
92
{
93
now++; t=
findwho(now);
94
ts[t-m][i+j-t+m]=
1
;
95
}
96
97
for
(
int
i=
1
;i<=n;i++
)
98
{
99
for
(
int
j=
1
;j<=n;j++
)
100
printf(
"
%d
"
,ts[i][j]);
101
puts(
""
);
102
}
103
}
104
105
inline
void
prep()
106
{
107
for
(
int
i=
1
;i<=
110
;i++) fx[i]=i*i,cha[i]=fx[i]-fx[i-
1
];
108
}
109
110
int
main()
111
{
112
prep();
113
read();
114
go();
115
return
0
;
116
}
