2597: [Wc2007]剪刀石头布
分析:
费用流。
首先转化一下问题,整张图最优的情况是存在$C_n^3$个,即任意3个都行,然后考虑去掉最少不满足的三元环。
如果u赢了v,u向v连一条边,如果v有k条入边,那么说明少了$C_k^2$个三元环,所对每场比赛分配度数,求最小费用最大流。
具体地:S向每场比赛连容量为1,花费为0的边;每场比赛向两个人连容量为1,花费为0的边;每个人因为度数不同,花费不同,所以差分后建边。
还有一种随机化+迭代的做法。
代码:
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<cctype>
#include<set>
#include<queue>
#include<vector>
#include<map>
using namespace std;
typedef long long LL; inline int read() {
int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;
for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;
} const int N = , INF = 1e9;
struct Edge { int from, to, nxt, cap, cost; } e[];
int head[N], pre[N], dis[N], q[], deg[N], id[][], A[][], P[N], tag[N], En = , S, T;
bool vis[N]; inline void add_edge(int u,int v,int f,int w) {
++En; e[En].from = u, e[En].to = v, e[En].cap = f, e[En].cost = w, e[En].nxt = head[u]; head[u] = En;
++En; e[En].from = v, e[En].to = u, e[En].cap = , e[En].cost = -w, e[En].nxt = head[v]; head[v] = En;
}
bool spfa() {
for (int i = ; i <= T; ++i) dis[i] = INF, vis[i] = false, pre[i] = ;
int L = , R = ;
q[++R] = S, vis[S] = true, dis[S] = ;
while (L <= R) {
int u = q[L ++]; vis[u] = false;
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (dis[v] > dis[u] + e[i].cost && e[i].cap > ) {
dis[v] = dis[u] + e[i].cost;
pre[v] = i;
if (!vis[v]) q[++R] = v, vis[v] = true;
}
}
}
return dis[T] != INF;
}
int mcf() {
int Cost = , Flow = ;
while (spfa()) {
int now = 1e9;
for (int i = T; i != S; i = e[pre[i]].from)
now = min(now, e[pre[i]].cap);
for (int i = T; i != S; i = e[pre[i]].from)
e[pre[i]].cap -= now, e[pre[i] ^ ].cap += now;
Cost += dis[T] * now;
Flow += now;
}
return Cost;
}
int main() {
freopen("a.in", "r", stdin);
int n = read(), tot = n;
if (n < ) { printf(""); return ; }
for (int i = ; i <= n; ++i) {
for (int j = ; j <= i; ++j) read();
for (int j = i + ; j <= n; ++j) {
int x = read();
id[i][j] = ++tot;
if (x == ) deg[j] ++, tag[tot] = ;
else if (x == ) deg[i] ++, tag[tot] = ;
else { add_edge(tot, i, , ); P[tot] = En; add_edge(tot, j, , ); }
}
}
S = , T = tot + ;
for (int i = n + ; i <= tot; ++i) add_edge(S, i, , );
for (int i = ; i <= n; ++i)
for (int j = deg[i]; j < n - ; ++j) add_edge(i, T, , j);
int ans = n * (n - ) * (n - ) / ;
for (int i = ; i <= n; ++i)
ans -= deg[i] * (deg[i] - ) / ;
ans -= mcf();
printf("%d\n", ans);
for (int i = ; i <= n; ++i)
for (int j = i + ; j <= n; ++j) {
if (tag[id[i][j]]) A[i][j] = tag[id[i][j]] - ;
else A[i][j] = e[P[id[i][j]]].cap ? : ;
}
for (int i = ; i <= n; ++i, puts("")) {
for (int j = ; j < i; ++j) printf("%d ", A[j][i] ^ );
for (int j = i; j <= n; ++j) printf("%d ", A[i][j]);
}
return ;
}