CodeChef RIN

Description

你有 $m$ 个学期来完成 $n$ 个课程，每个学期能上任意多课程，每个课程恰好被学一遍。有些课程有前置条件，必须先学 $a$ 课程才能学 $b$ 课程。在第 $i$ 个学期完成第 $j$ 这个课程能够获得 $A[i][j]$ 的分数（$A[i][j]=-1$ 说明 $i$ 学期不教授 $j$ 课程）。求最大的平均分数。

Solution

类似于切糕的建图方式，把每个课程拆成 $m + 1$ 个点。令第 $i$个课程拆出来的第 $j$ 个点事 $(i, j)$

对于一个课程 $i$ ，有以下的建图方式：

• $(i, j) \to (i,j+1)$ 连流量 $100 - A[i][j]$ 的边
• $S \to (i,1)$ 和 $(i,m+1) \to T$ 都连一条流量为 INF 的边
• 如果已知两个课程 $a,b$ 必须使得 $a$ 是 $b$ 的前置课程，那么对于 $1 \leq i \leq m-1$ 连一条 $(a,i) \to (b,i+1)$ 的流量为 INF 的边

然后跑出最大流，再用 $100 - \frac{\text{最大流}}{n}$

为什么这是对的呢？首先，总分最大就是使得减分最小，所以把每个分数用最大值($\leq 100$) 减一下跑出最小割然后用总和减掉。此时 $A[i][j]$ 就变成了 $i$ 课程在 $j$ 学期的扣分。

对于每一条学期，我们必须上一次课，在最小割中体现就是对这个学期建立一条链，割了第 $j$ 个点和第 $j+1$ 个点之间的边表示在 $j$ 这个学期上了这个课。每条链显然只会恰好割一次。

对于前置条件的限制，在最小割中的体现便是 $a$ 学期的割边在 $b$ 学期之前。那么按照第三种连边使得如果不在 $b$ 前面那么必然会有一条通路（画图理解）。

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 10010000; 
const int INF = (int)2e9; 

int n, m, k; 

int S, T, vis[N]; 

struct edge {
  int v, f; edge *next, *rev; 
} pool[N * 2], *h[N], *cu = pool, *cur[N]; 

void addedge(int u, int v, int f) {
  edge *p = cu++, *q = cu++; 
  p->v = v, p->next = h[u], h[u] = p, p->f = f, p->rev = q; 
  q->v = u, q->next = h[v], h[v] = q, q->f = 0, q->rev = p; 
}

int dep[N], Q[N];

bool bfs() {
  for(int i = S; i <= T; i++) 
    cur[i] = h[i], dep[i] = 0; 
  int s = 1, t = 0; dep[S] = 1, Q[++t] = S; 
  while(s <= t) {
    int u = Q[s++]; 
    for(edge *p = h[u]; p; p = p->next) {
      int v = p->v; if(p->f && !dep[v]) {
        Q[++t] = v, dep[v] = dep[u] + 1; 
        if(v == T) return 1; 
      }
    }
  } return 0; 
}

int dfs(int u, int lim) {
  if(u == T || !lim) return lim; int ret = 0; 
  for(edge *p = cur[u]; p; p = p->next) { cur[u] = p; 
    int v = p->v; if(p->f && dep[v] == dep[u] + 1) {
      int tmp = dfs(v, min(lim, p->f)); 
      p->f -= tmp, p->rev->f += tmp; 
      ret += tmp, lim -= tmp; 
    }
  } if(!ret) dep[u] = -1; 
  return ret; 
}

int dinic() {
  int ret = 0; 
  while(bfs()) ret += dfs(S, INF); 
  return ret; 
}

int a[1005][1005]; 
int dx[8] = {1, 1, 2, 2, -1, -1, -2, -2}; 
int dy[8] = {2, -2, 1, -1, 2, -2, 1, -1}; 

int id(int x, int y) {
  return (x - 1) * (m + 1) + y; 
}

int main() {
  cin >> n >> m >> k; 
  for(int i = 1; i <= n; i++) 
    for(int j = 1; j <= m; j++) 
      cin >> a[i][j];  
  S = 0; T = n * (m + 1) + 1; 
  for(int i = 1; i <= n; i++) {
    addedge(S, id(i, 1), INF); 
    for(int j = 1; j <= m; j++) {
      if(a[i][j] != -1) addedge(id(i, j), id(i, j + 1), 100 - a[i][j]); 
      else addedge(id(i, j), id(i, j + 1), INF); 
    } addedge(id(i, m + 1), T, INF); 
  }
  for(int i = 1; i <= k; i++) {
    int x, y; cin >> x >> y; 
    for(int j = 1; j <= m; j++) 
      addedge(id(x, j), id(y, j + 1), INF); 
  } 
  printf("%.2lf\n", 1.0 * 100 - 1.0 * dinic() / (1.0 * n)); 
  return 0; 
}