BZOJ 2597 剪刀石头布（最小费用最大流）（WC2007） - Oyking - 博客园

1 #include

2 #include

3 #include

4 #include

5 #include

6 using namespace std;

7

8 const int MAXN = 110;

9 const int MAXV = MAXN * MAXN;

10 const int MAXE = MAXN * MAXV;

11 const int INF = 0x7f7f7f7f;

12

13 struct ZWK_FLOW {

14 int head[MAXV], dis[MAXV];

15 int to[MAXE], next[MAXE], flow[MAXE], cost[MAXE];

16 int n, ecnt, st, ed;

17

18 void init() {

19 memset(head, 0, sizeof(head));

20 ecnt = 2;

21 }

22

23 void add_edge(int u, int v, int c, int w) {

24 to[ecnt] = v; flow[ecnt] = c; cost[ecnt] = w; next[ecnt] = head[u]; head[u] = ecnt++;

25 to[ecnt] = u; flow[ecnt] = 0; cost[ecnt] = -w; next[ecnt] = head[v]; head[v] = ecnt++;

26 //printf("%d %d %d %d

", u, v, c, w);

27 }

28

29 void spfa() {

30 for(int i = 1; i <= n; ++i) dis[i] = INF;

31 priority_queue > que;

32 dis[st] = 0; que.push(make_pair(0, st));

33 while(!que.empty()) {

34 int u = que.top().second, d = -que.top().first; que.pop();

35 if(d != dis[u]) continue;

36 for(int p = head[u]; p; p = next[p]) {

37 int &v = to[p];

38 if(flow[p] && dis[v] > d + cost[p]) {

39 dis[v] = d + cost[p];

40 que.push(make_pair(-dis[v], v));

41 }

42 }

43 }

44 int t = dis[ed];

45 for(int i = 1; i <= n; ++i) dis[i] = t - dis[i];

46 }

47

48 int minCost, maxFlow;

49 bool vis[MAXV];

50

51 int add_flow(int u, int aug) {

52 if(u == ed) {

53 maxFlow += aug;

54 minCost += dis[st] * aug;

55 return aug;

56 }

57 vis[u] = true;

58 int now = aug;

59 for(int p = head[u]; p; p = next[p]) {

60 int &v = to[p];

61 if(flow[p] && !vis[v] && dis[u] == dis[v] + cost[p]) {

62 int t = add_flow(v, min(now, flow[p]));

63 flow[p] -= t;

64 flow[p ^ 1] += t;

65 now -= t;

66 if(!now) break;

67 }

68 }

69 return aug - now;

70 }

71

72 bool modify_label() {

73 int d = INF;

74 for(int u = 1; u <= n; ++u) if(vis[u]) {

75 for(int p = head[u]; p; p = next[p]) {

76 int &v = to[p];

77 if(flow[p] && !vis[v]) d = min(d, dis[v] + cost[p] - dis[u]);

78 }

79 }

80 if(d == INF) return false;

81 for(int i = 1; i <= n; ++i) if(vis[i]) dis[i] += d;

82 return true;

83 }

84

85 int min_cost_flow(int ss, int tt, int nn) {

86 st = ss, ed = tt, n = nn;

87 minCost = maxFlow = 0;

88 spfa();

89 while(true) {

90 while(true) {

91 for(int i = 1; i <= n; ++i) vis[i] = false;

92 if(!add_flow(st, INF)) break;

93 }

94 if(!modify_label()) break;

95 }

96 return minCost;

97 }

98 } G;

99

100 int n, m;

101 int mat[MAXN][MAXN], ans[MAXN][MAXN];

102

103 inline int encode(int i, int j) {

104 if(i > j) swap(i, j);

105 return i * n + j;

106 }

107

108 int main() {

109 scanf("%d", &n);

110 for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) scanf("%d", &mat[i][j]);

111 m = n * n;

112 int ss = n + m + 1, tt = ss + 1;

113 G.init();

114 int sum = n * (n - 1) * (n - 2) / 6;

115 for(int i = 1; i <= n; ++i) {

116 for(int j = 1, tmp = 1; j < n; ++j, tmp += 2) G.add_edge(ss, i, 1, tmp);

117 for(int j = 1; j <= n; ++j) if(mat[i][j] != 0)

118 ans[i][j] = G.ecnt, G.add_edge(i, encode(i, j), 1, 0);

119 }

120 for(int i = 1; i <= m; ++i) G.add_edge(i + n, tt, 1, 0);

121 int x = G.min_cost_flow(ss, tt, tt);

122 printf("%d

", sum - (x - n * (n - 1) / 2) / 2);

123 for(int i = 1; i <= n; ++i) {

124 for(int j = 1; j <= n; ++j) {

125 if(j != 1) printf(" ");

126 if(mat[i][j] != 2) printf("%d", mat[i][j]);

127 else {

128 if(G.flow[ans[i][j]] == 0) printf("1");

129 else printf("0");

130 }

131 }

132 puts("");

133 }

134 }