【易懂】费用流【SDOI2009】晨跑

【SDOI2009】晨跑

题面

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

Sample Output

2 11

Data Constraint

Hint

数据范围：
对于30%的数据，N ≤ 20，M ≤ 120。
对于100%的数据，N ≤ 200，M ≤ 20000。

费用流

（默认你已经会了最大流）

费用流，即在最大流的基础上，选择权值min值.

我们可以用spfa做最大流（近似ek），权值=单价*距离

代码奉上

 1 bool bfs(int s,int t)
 2 {
 3     f(i,1,2*n)
 4     {
 5         dis[i]=flow[i]=inf;
 6     }
 7     int head=0,tail=1;
 8     c[1]=s;vis[s]=++tot;
 9     dis[s]=0;fa[t]=-1;
10     while(head<tail)
11     {
12         int x=c[++head];
13         vis[x]=0;
14         for(int i=h[x];i;i=e[i].next)
15         {
16             int y=e[i].to;
17             if(e[i].flow&&dis[x]+e[i].dis<dis[y])
18             {
19                 dis[y]=dis[x]+e[i].dis;
20                 fa[y]=x;
21                 last[y]=i;
22                 flow[y]=min(flow[x],(long long)e[i].flow);
23                 if(vis[y]!=tot)
24                 {
25                     vis[y]=tot;
26                     c[++tail]=y;
27                 }
28             }
29         }
30     }
31     return fa[t]!=-1;
32 }
33 void mcmf(int s,int t)
34 {
35     while(bfs(s,t))
36     {
37         maxflow+=flow[t];
38         mincost+=flow[t]*dis[t];
39         for(int i=fa[t];i!=s;i=fa[i])
40         {
41             e[last[i]].flow-=flow[t];
42             e[last[i]^1].flow+=flow[t];
43         }
44     }
45 }

费用流spfa

本题思路

网络流难在建图，核心部分copy就好了：

由于本题特殊性，我们采用割点，即x->y+n->n

并且每条边流量为1/0

如下图，前者为流量，后者为权值

然后跑一边费用流即可

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring> 
 4 #define inf 1000000000
 5 #define S 1
 6 #define T n
 7 #define f(i,a,b) for(register int i=a,x,y,z;i<=b;++i)
 8 #define read(a) scanf("%d",&a)
 9 using namespace std;
10 int n,m,h[1005],cnt=1,fa[1005];
11 long long ans,flow[1005],tot,c[10005],vis[1005],dis[1005],last[1005],maxflow,mincost;
12 struct node
13 {
14     int next,to,flow,dis;
15 }e[100005];
16 void add(int x,int y,int flow,int dis)
17 {
18     e[++cnt].to=y;
19     e[cnt].flow=flow;
20     e[cnt].dis=dis;
21     e[cnt].next=h[x];
22     h[x]=cnt;
23 }
24 bool bfs(int s,int t)
25 {
26     f(i,1,2*n)
27     {
28         dis[i]=flow[i]=inf;
29     }
30     int head=0,tail=1;
31     c[1]=s;vis[s]=++tot;
32     dis[s]=0;fa[t]=-1;
33     while(head<tail)
34     {
35         int x=c[++head];
36         vis[x]=0;
37         for(int i=h[x];i;i=e[i].next)
38         {
39             int y=e[i].to;
40             if(e[i].flow&&dis[x]+e[i].dis<dis[y])
41             {
42                 dis[y]=dis[x]+e[i].dis;
43                 fa[y]=x;
44                 last[y]=i;
45                 flow[y]=min(flow[x],(long long)e[i].flow);
46                 if(vis[y]!=tot)
47                 {
48                     vis[y]=tot;
49                     c[++tail]=y;
50                 }
51             }
52         }
53     }
54     return fa[t]!=-1;
55 }
56 void mcmf(int s,int t)
57 {
58     while(bfs(s,t))
59     {
60         maxflow+=flow[t];
61         mincost+=flow[t]*dis[t];
62         for(int i=fa[t];i!=s;i=fa[i])
63         {
64             e[last[i]].flow-=flow[t];
65             e[last[i]^1].flow+=flow[t];
66         }
67     }
68 }
69 int main()
70 {
71     read(n);read(m);
72     f(i,1,m)
73     {
74         read(x);
75         read(y);
76         read(z);
77         add(x,y+n,1,z);
78         add(y+n,x,0,-z);
79     }
80     f(i,1,n)
81     {
82         add(i+n,i,1,0);
83         add(i,i+n,0,0);
84     }
85     mcmf(S,T);
86     printf("%lld %lld",maxflow,mincost);
87 }

【SDOI2009】晨跑