2018牛客多校05 E room (费用流)

发表于 | 更新于 | 分类于 ， | 评论数： | 阅读次数：

链接：https://www.nowcoder.com/acm/contest/143/E

n个宿舍，每个宿舍住4个人，给两年的住宿情况，问最少调换多少人，能从前一年的住宿状态调换到后一年的住宿状态（宿舍顺序不影响）。

比赛的时候没时间看，补题的时候发现是一道挺好想的费用流问题。

考虑宿舍整体，当一个宿舍变为另一个宿舍的时候，我们的代价是这两个宿舍中不同人的个数，按照这条规律，我们可以建图：

单独建超级源和超级汇，之后按照不同年份和不同宿舍建点，不同年的每个宿舍之间连接一条边，容量为1，费用为不同人的个数。源点连接前一年的点，容量为1费用为0，后一年的点连汇点，容量为1费用为0。这样跑一下最小费用最大流就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef struct Node {
  int u, v, next;
  LL c, w;
}Node;
const int maxn = 210;
const int maxm = 40100;
const LL mod = 0x3f3f3f3fLL;
const LL inf = (1LL<<55);
int tot, head[maxn];
LL dist[maxn];
LL cost, flow;
Node e[maxm];
int pre[maxn];
bool visit[maxn];
queue<int> Q;
int S, T, N;

void init() {
  S = T = N = 0;
  memset(head, -1, sizeof(head));
  tot = 0;
}

void adde(int u, int v, LL c, LL w) {
  e[tot].u = u; e[tot].v = v; e[tot].c = c; e[tot].w = w; e[tot].next = head[u]; head[u] = tot++;
  e[tot].u = v; e[tot].v = u; e[tot].c = 0; e[tot].w = -w; e[tot].next = head[v]; head[v] = tot++;
}
bool spfa(int s, int t, int n) {
  int i;
  for(i = 0; i <= n; i++) {
    dist[i] = inf;
    visit[i] = 0;
    pre[i] = -1;
  }
  while(!Q.empty()) Q.pop();
  Q.push(s);
  visit[s] = true;
  dist[s] = 0;
  pre[s] = -1;
  while(!Q.empty()) {
    int u = Q.front();
    visit[u] = false;
    Q.pop();
    for(int j = head[u]; j != -1; j = e[j].next) {
      if(e[j].c > 0 && dist[u] + e[j].w < dist[e[j].v]) {
        dist[e[j].v] = dist[u] + e[j].w;
        pre[e[j].v] = j;
        if(!visit[e[j].v]) {
          Q.push(e[j].v);
          visit[e[j].v] = true;
        }
      }
    }
  }
  // return dist[t] < 0; // 求可行流
  if(dist[t] == inf) return false;  // 求最小费用流
  else return true;
}
LL ChangeFlow(int t) {
  LL det = mod;
  int u = t;
  while(~pre[u]) {
    u = pre[u];
    det = min(det, e[u].c);
    u = e[u].u;
  }
  u = t;
  while(~pre[u]) {
    u = pre[u];
    e[u].c -= det;
    e[u ^ 1].c += det;
    u = e[u].u;
  }
  return det;
}
LL MinCostFlow(int s, int t, int n) {
  LL mincost, maxflow;
  mincost = maxflow = 0;
  while(spfa(s, t, n)) {
    LL det = ChangeFlow(t);
    mincost += det * dist[t];
    maxflow += det;
  }
  cost = mincost;
  flow = maxflow;
  return mincost;
}

int n;
int vis[maxn][maxn][2];

signed main() {
  // freopen("in", "r", stdin);
  int x;
  while(~scanf("%d", &n)) {
    init();T = 2 * n + 1; N = T + 1;
    memset(vis, 0, sizeof(vis));
    int tot = n * 4;
    for(int i = 1; i <= n; i++) {
      for(int j = 1; j <= 4; j++) {
        scanf("%d", &x);
        vis[i][x][0] = 1;
      }
    }
    for(int i = 1; i <= n; i++) {
      for(int j = 1; j <= 4; j++) {
        scanf("%d", &x);
        vis[i][x][1] = 1;
      }
    }
    for(int i = 1; i <= n; i++) {
      adde(S, i, 1, 0);
      adde(i+n, T, 1, 0);
    }
    for(int i = 1; i <= n; i++) {
      for(int j = 1; j <= n; j++) {
        int diff = 0;
        for(int k = 1; k <= tot; k++) {
          if(vis[i][k][0] == vis[j][k][1] && vis[i][k][0] == 1) {
            diff++;
          }
        }
        adde(i, j+n, 1, 4-diff);
      }
    }
    cout << MinCostFlow(S, T, N) << endl;
  }
  return 0;
}