自动搬运

查看原文

来自洛谷，原作者为

	Imagine 自闭了自闭了。

搬运于2025-08-24 21:58:10，当前版本为作者最后更新于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$）。

最后的输出方案，对于未定向边，只需看费用流的图中，边对应的点指向的两个图上结点的边中哪一条满流即可。

代码

#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;
}