BZOJ1877【SDOI2009】晨跑 <拆点费用流>

Problem

【SDOI2009】晨跑

$\mathrm{Time\;Limit:\;4\;Sec}$
$\mathrm{Memory\;Limit:\;64\;MB}$

Description

$Elaxia$最近迷恋上了空手道，他为自己设定了一套健身计划，比如俯卧撑、仰卧起坐等 等，不过到目前为止，他坚持下来的只有晨跑。 现在给出一张学校附近的地图，这张地图中包含$N$个十字路口和$M$条街道，$Elaxia$只能从 一个十字路口跑向另外一个十字路口，街道之间只在十字路口处相交。$Elaxia$每天从寝室出发 跑到学校，保证寝室编号为$1$，学校编号为$N$。 $Elaxia$的晨跑计划是按周期（包含若干天）进行的，由于他不喜欢走重复的路线，所以在一个周期内，每天的晨跑路线都不会相交（在十字路口处），寝室和学校不算十字路 口。$Elaxia$耐力不太好，他希望在一个周期内跑的路程尽量短，但是又希望训练周期包含的天数尽量长。 除了练空手道，$Elaxia$其他时间都花在了学习和找$MM$上面，所有他想请你帮忙为他设计 一套满足他要求的晨跑计划。

Input

第一行：两个数$N,M$。表示十字路口数和街道数。
接下来$M$行，每行$3$个数$a,b,c$，表示路口$a$和路口$b$之间有条长度为$c$的街道（单向）。

Output

两个数，第一个数为最长周期的天数，第二个数为满足最长天数的条件下最短的路程长度。

Sample Input

7 10
1 2 1
1 3 1
2 4 1
3 4 1
4 5 1
4 6 1
2 5 5
3 6 6
5 7 1
6 7 1

Sample Output

2 11

Hint

$N\le 200, M\le 20000$。

标签：拆点费用流

Solution

拆点费用流套路题。
首先要同时考虑天数最长和路程最短两个权，可知要用费用流。
看到每个点只经过一次可知要把每个点拆成入点和出点，中间连流量为$1$费用为$0$的边。
套路建图后跑费用流即可。

Code

#include <bits/stdc++.h>
#define MAX_N 500
#define MAX_M 50000
#define INF 0x7f7f7f7f
using namespace std;
int n, m, s, t, cnt, pr[MAX_N+5], cr[MAX_N+5], mxf, mic;
struct node {int v, c, w, nxt;} E[MAX_M+5];
void init() {s = 1, t = n+n, memset(pr, -1, sizeof pr);}
void insert(int u, int v, int c, int w) {E[cnt] = (node){v, c, w, pr[u]}, pr[u] = cnt++;}
void addedge(int u, int v, int c, int w) {insert(u, v, c, w), insert(v, u, 0, -w);}
bool SPFA() {
    queue <int> que;	bool inq[MAX_N+5];	int d[MAX_N+5], cr[MAX_N+5];
    memset(inq, false, sizeof inq), memset(d, INF, sizeof d), memset(cr, -1, sizeof cr);
    d[s] = 0, que.push(s), inq[s] = true;
    while (!que.empty()) {
        int u = que.front();	que.pop(), inq[u] = false;
        for (int i = pr[u]; ~i; i = E[i].nxt) {
            int v = E[i].v, c = E[i].c, w = E[i].w;
            if (c && d[u]+w < d[v]) {
                d[v] = d[u]+w, cr[v] = i;
                if (!inq[v]) que.push(v), inq[v] = true;
            }
        }
    }
    if (d[t] == INF) return false;	int flow = INF;
    for (int i = cr[t]; ~i; i = cr[E[i^1].v]) flow = min(flow, E[i].c);
    for (int i = cr[t]; ~i; i = cr[E[i^1].v]) E[i].c -= flow, E[i^1].c += flow;
    mxf += flow, mic += d[t];	return true;
}
int main() {
    scanf("%d%d", &n, &m), init();
    addedge(1, 1+n, INF, 0), addedge(n, n+n, INF, 0);
    for (int i = 2; i < n; i++) addedge(i, i+n, 1, 0);
    for (int i = 0, u, v, w; i < m; i++)
        scanf("%d%d%d", &u, &v, &w), addedge(u+n, v, 1, w);
    while (SPFA()) ;	return printf("%d %d", mxf, mic), 0;
}