luogu P4249 [WC2007]剪刀石头布

https://www.luogu.com.cn/problem/P4249

考虑啥限制都没有的情况，方案数是$\left(\genfrac{}{}{0ex}{}{n}{3}\right)=\frac{n(n?1)(n?2)}{6}$

一个三元环$(a,b,c)$是长啥样的？容易发现就是三个点入度出度都是$1$

那么一个三元组不构成三元环是怎样的？容易发现一定是有一个点出度为$2$,一个点入度为$2$

这里只用考虑入度就行了，也就是只要有一个点入度为$2$，那么就会少一个三元环
同理，如果一个点入度为$3$,就会少$3$个三元环

不难得到$$ANS=\frac{n(n?1)(n?2)}{6}?\sum _u\left(\genfrac{}{}{0ex}{}{in[u]}{2}\right)$$

直接搞度数也不是很好弄，考虑差分，$\left(\genfrac{}{}{0ex}{}{in[u]}{2}\right)?\left(\genfrac{}{}{0ex}{}{in[u]?1}{2}\right)=in[u]?1$也就是如果入度为$in[u]$，会比入度为$in[u]?1$的少这么多个三元组

因为入度出度一定是相同的，考虑网络流建模一定是满流的，在满流的情况下要使后面那个东西最小，可以考虑费用流

把边放一边，点放一边，形成一个二分图

如果$a[i][j]=2$源点$S$像每条边连(1,0)的边，然后这条边向$u,v$两点分别连$(1,0)$的边
否则原点直接向入度点连$(1,0)$边

然后对于每个点，向汇点$T$连$n$条边，边权为$(1,i?1)$表示每个度数相对上一个度数新增的费用，因为是最小费用最大流，所以一定会选一个前缀的边流

输出方案看流量就好了
代码实现不难
code:

#include<bits/stdc++.h>
#define N 1005
using namespace std;
struct edge {
    int v, c, w, nxt;
} e[N * N << 1];
int p[N * N], eid;
void init() {
    memset(p, -1, sizeof p);eid = 0;
}
void insert(int u, int v, int c, int w) {
    e[eid].v = v;e[eid].c = c;e[eid].w = w;e[eid].nxt = p[u];p[u] = eid ++;
}
void add(int u, int v, int c, int w) {
    // printf("%d %d %d\n", u, v, c);insert(u, v, c, w);insert(v, u, 0, - w);
}
int S, T, n, pre[N * N], dis[N * N], vis[N * N], a[N][N];
const int inf = 1e9;
queue<int> q;
int bfs() {
    for(int i = 0; i <= T; i ++) pre[i] = -1, dis[i] = inf, vis[i] = 0;q.push(S), dis[S] = 0;while(q.size()) {
    int u = q.front(); q.pop();vis[u] = 0;for(int i = p[u]; i + 1; i = e[i].nxt) {
    int v = e[i].v, c = e[i].c, w = e[i].w;if(c && dis[u] + w < dis[v]) {
    dis[v] = dis[u] + w;pre[v] = i;if(!vis[v]) vis[v] = 1, q.push(v);   }}}//for(int i = 1; i <= T; i ++) printf("%d ", e[pre[i] ^ 1].v); printf("\n");return pre[T] != -1;
}
int mcmf() {
    int ret = 0;for(; bfs() ;) {
    int flow = inf;for(int i = T; i != S; i = e[pre[i] ^ 1].v) flow = min(flow, e[pre[i]].c);for(int i = T; i != S; i = e[pre[i] ^ 1].v) {
    ret += flow * e[pre[i]].w;e[pre[i]].c -= flow, e[pre[i] ^ 1].c += flow;}}return ret;
}
int id(int x, int y) {
    return x * n + y;
}
int main() {
    // freopen("a.in","r",stdin);// freopen("a.out","w",stdout);init();scanf("%d", &n); S = n * n + n + 1, T = S + 1;for(int i = 1; i <= n; i ++) for(int j = 1; j <= n; j ++) {
    scanf("%d", &a[i][j]);if(i >= j) continue;if(a[i][j] == 0) add(S, i, 1, 0);else if(a[i][j] == 1) add(S, j, 1, 0);else {
    add(S, id(i, j), 1, 0);add(id(i, j), i, 1, 0);add(id(i, j), j, 1, 0);}}for(int i = 1; i <= n; i ++) {
    for(int j = 1; j <= n; j ++) add(i, T, 1, j - 1);}printf("%d\n", n * (n - 1) * (n - 2) / 6 - mcmf());for(int i = 1; i <= n; i ++) {
    for(int j = i + 1; j <= n; j ++) if(a[i][j] == 2) {
    int x = id(i, j);for(int k = p[x]; k + 1; k = e[k].nxt) {
    if(e[k ^ 1].c && e[k].v != S) {
    if(e[k].v == j) a[i][j] = 1;else a[i][j] = 0;a[j][i] = !a[i][j];}}}}for(int i = 1; i <= n; i ++) {
    for(int j = 1; j <= n; j ++) printf("%d ", a[i][j]); printf("\n");}return 0;
}