题解 P4249 【[WC2007]剪刀石头布】
Imagine
2018-03-06 21:36:52
## 题目大意
竞赛图中的部分边方向已确定，你需要决定剩余边的方向，使得整个图上的三元环数量最多。
## 题解
从整个图的 $n$个点中任取 $3$个点，方案数为$$C^{3}_{n}=\frac{n!}{3!(n-3)!}=\frac{n(n-1)(n-2)}{6}$$
考虑 $3$个点不构成三元环的情况，必然为一点的入度为 $2$，一点的出度为
$2$，一点的入度出度为 $1$。不妨从入度入手，一个点若入度为 $2$，则表明失去了一个三元环，若入度为 $3$，则会失去 $3$个三元环（考虑点 $A$被点 $B, C, D$通过边指向，那么 $(A,B,C), (A,B,D), (A,C,D)$都不会是三元环），因此，对于一个点 $u$而言，记其入度为 $degree(u)$，那么点 $u$会使整张图会失去
$C^{2}_{degree(u)}$个三元环。故对于最终答案 $ans$，有
$$ans = \frac{n(n-1)(n-2)}{6} - \sum_{u \in V}{C^{2}_{degree(u)}}$$
通过上述过程已经能够发现，对于一个点 $u$，考虑差分，若其入度增加 $1$，则会使整个图失去的三元环个数为 $$C^{2}_{degree(u)} - C^{2}_{degree(u)-1} = degree(u)-1$$因此，可以将失去的三元环作费用，跑费用流。
我们对于未定向的边，将其视为点（以下称作「边对应的点」），建图如下：
$1.$ 由源点 $s$向每一条边对应的点连边，容量为 $1$，费用为 $0$；
$2.$ 由每一条边对应的点向该边连接的两个图上结点连边，容量为 $1$，费用为
$0$，表明该条边只会使得其中一个点入度 $+1$；
$3.$ 由每一个图上结点向汇点 $t$连若干条边，费用依次为 $0, 1, 2, 3......$（分别表示该点入度从 $0$开始每增加 $1$就会失去的三元环数量），容量均为 $1$（注意初始图的处理，即某些点初始入度不为 $0$）。
最后的输出方案，对于未定向边，只需看费用流的图中，边对应的点指向的两个图上结点的边中哪一条满流即可。
## 代码
```cpp
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 5150 + 10;
const int maxg = 100 + 10;
const int INF = 1000000000;
int n;
int s, t;
int rel[maxg][maxg];
int wedge[maxg][maxg];
int indeg[maxn];
int edgeidx(int x, int y) {
return (2*n-x) * (x-1) / 2 + (y-x) + n;
}
struct Edge {
int from, to, cap, flow, cost;
Edge(int from, int to, int cap, int flow, int cost):
from(from), to(to), cap(cap), flow(flow), cost(cost) {}
};
template <int maxn> struct MCMF {
int n, m, s, t;
vector <Edge> edges;
vector <int> G[maxn];
int inq[maxn];
int d[maxn];
int p[maxn];
int a[maxn];
void init(int n) {
this->n = n;
for(int i = 0; i < n; i++) G[i].clear();
edges.clear();
}
void AddEdge(int from, int to, int cap, int cost) {
edges.push_back(Edge(from, to, cap, 0, cost));
edges.push_back(Edge(to, from, 0, 0, -cost));
m = edges.size();
G[from].push_back(m-2);
G[to].push_back(m-1);
}
bool BellmanFord(int s, int t, int& cost) {
for(int i = 0; i < n; i++) d[i] = INF;
memset(inq, 0, sizeof(inq));
d[s] = 0; inq[s] = 1; p[s] = 0; a[s] = INF;
queue <int> Q;
Q.push(s);
while(!Q.empty()) {
int u = Q.front(); Q.pop();
inq[u] = 0;
for(int i = 0; i < G[u].size(); i++) {
Edge& e = edges[G[u][i]];
if(e.cap > e.flow && d[e.to] > d[u] + e.cost) {
d[e.to] = d[u] + e.cost;
p[e.to] = G[u][i];
a[e.to] = min(a[u], e.cap - e.flow);
if(!inq[e.to]) { Q.push(e.to); inq[e.to] = 1; }
}
}
}
if(d[t] == INF) return false;
cost += d[t] * a[t];
int u = t;
while(u != s) {
edges[p[u]].flow += a[t];
edges[p[u]^1].flow -= a[t];
u = edges[p[u]].from;
}
return true;
}
int Mincost(int s, int t) {
int cost = 0;
while(BellmanFord(s, t, cost));
return cost;
}
};
MCMF <maxn> solver;
int main() {
scanf("%d", &n);
s = 0; t = (n+1)*n/2 + n + 1;
solver.init(t+1);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++) {
scanf("%d", &rel[i][j]);
if(rel[i][j] == 1) indeg[j]++;
}
for(int i = 1; i <= n; i++)
for(int j = i+1; j <= n; j++) {
if(rel[i][j] < 2) continue;
solver.AddEdge(s, edgeidx(i, j), 1, 0);
solver.AddEdge(edgeidx(i, j), i, 1, 0);
wedge[j][i] = solver.m - 2;
solver.AddEdge(edgeidx(i, j), j, 1, 0);
wedge[i][j] = solver.m - 2;
}
int down = 0;
for(int i = 1; i <= n; i++) {
down += indeg[i] * (indeg[i]-1) / 2;
for(int j = indeg[i] + 1; j < n; j++)
solver.AddEdge(i, t, 1, j-1);
}
down += solver.Mincost(s, t);
printf("%d\n", n*(n-1)*(n-2) / 6 - down);
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(rel[i][j] < 2) printf("%d", rel[i][j]);
else printf("%d", solver.edges[wedge[i][j]].flow);
if(j < n) printf(" ");
}
printf("\n");
}
return 0;
}
```