BZOJ#1877. [SDOI2009]晨跑

题目描述

Elaxia最近迷恋上了空手道，他为自己设定了一套健身计划，比如俯卧撑、仰卧起坐等等，不过到目前为止，他

坚持下来的只有晨跑。现在给出一张学校附近的地图，这张地图中包含N个十字路口和M条街道，Elaxia只能从一

个十字路口跑向另外一个十字路口，街道之间只在十字路口处相交。Elaxia每天从寝室出发跑到学校，保证寝室

编号为1，学校编号为N。 Elaxia的晨跑计划是按周期（包含若干天）进行的，由于他不喜欢走重复的路线，所以

在一个周期内，每天的晨跑路线都不会相交（在十字路口处），寝室和学校不算十字路口。Elaxia耐力不太好，

他希望在一个周期内跑的路程尽量短，但是又希望训练周期包含的天数尽量长。除了练空手道，Elaxia其他时间

都花在了学习和找MM上面，所有他想请你帮忙为他设计一套满足他要求的晨跑计划。

输入格式

第一行：两个数N,M。表示十字路口数和街道数。

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

N ≤ 200，M ≤ 20000。

输出格式

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

样例输入输出

输入

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

输出

2 11

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <queue>
 5 const int N = 4e2 + 3, inf = 1 << 30, M = 2e4 + 4e2 + 3;
 6 using namespace std;
 7 int n, m, s, t, flow[N], vis[N], dis[N], pre[N],cnt,head[N],nxt[N];
 8 struct edge
 9 {
10     int fro,nxt,to,flo,val;
11 } E[100001];
12 
13 
14 void add(int u,int v,int ci,int vi)
15 {
16     E[++cnt] = (edge){u,head[u],v,ci,vi}; head[u] = cnt;
17     E[++cnt] = (edge){v,head[v],u,0,-vi}; head[v] = cnt;
18 }
19 
20 void Init()
21 {
22     cnt = -1; memset(head,-1,sizeof(head));
23     scanf("%d%d",&n,&m); s = 1, t = n + n ;
24     for(int i = 2; i < n; ++i) add(i,i+n,1,0);
25      add(n,t,inf,0); add(1,1+n,inf,0);
26     int u,v,vi;
27     for(int i = 1; i <= m; ++i)
28     {
29         scanf("%d%d%d",&u,&v,&vi);
30         add(u+n,v,1,vi);
31     }
32 }
33 
34 int Q[100001];
35 int spfa()
36 {
37     int l = 0, r = 0;
38     for(int i = s; i <= t; ++i) flow[i] = inf, dis[i] = inf, vis[i] = false;
39     dis[s] = 0, vis[s] = true; Q[++r] = s;
40     while(l != r)
41     {
42         ++l; if(l >= cnt) l = 1;
43         int u = Q[l]; vis[u] = false;
44         for(int i = head[u]; ~i; i = E[i].nxt)
45         {
46             int v = E[i].to; 
47             if(E[i].flo && dis[v] > dis[u] + E[i].val)
48             {            
49                 dis[v] = dis[u] + E[i].val; nxt[v] = i;
50                 flow[v] = min(flow[u],E[i].flo);
51                 if(vis[v]) continue;
52                 ++r; if(r >= cnt) r = 1;
53                 vis[v] = true; Q[r] = v;
54             }
55         
56         }
57     }
58     return flow[t] != inf;
59 }
60 
61 
62 void Solve()
63 {
64     int in, ans = 0, sum = 0;
65     while(spfa())
66     {
67         int k = t;  sum += flow[t]; in = flow[t];
68         while(k != s)
69         {
70             E[nxt[k]].flo -= in;
71             E[nxt[k]^1].flo += in;
72             ans += in*E[nxt[k]].val; 
73             k = E[nxt[k]].fro;
74         }
75     }
76     printf("%d %d
",sum,ans);
77 }
78 
79 int main()
80 {
81     Init();
82     Solve();
83     return 0;
84 }