【BZOJ 1877】 [SDOI2009]晨跑

1877: [SDOI2009]晨跑Time Limit:4 SecMemory Limit:64 MBSubmit:1231Solved:638[Submit][Status][Discuss]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 101 2 11 3 12 4 13 4 14 5 14 6 12 5 53 6 65 7 16 7 1

Sample Output

2 11

HINT

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

Source

Day1

费用流。

因为要求每个点最多经过一次，因此把每个十字路口拆点，连流量为1的边；

但是起点和终点可以经过无数次，因此起点和终点拆成的点连inf，并且从s到起点，终点到t分别连inf的边。

x,y有边相连，那么从x’到y连流量为，费用为路径长度的边。

最后最大流就是路径条数，最小费用就是最短路径和。

#include <iostream>#include <cstring>#include <cstdio>#include <algorithm>#include <cmath>#include <cstdlib>#define inf 0x3f3f3f3f#define M 400+5#include <queue>using namespace std;queue<int> q;int tot=1,s=0,t,n,m,d[M],h[M],inq[M],a[M],p[M];struct edge{int from,to,cap,flow,cost,ne;}E[200005];void Addedge(int x,int y,int cap,int cost){E[++tot]=(edge){x,y,cap,0,cost,h[x]};h[x]=tot;E[++tot]=(edge){y,x,0,0,-cost,h[y]};h[y]=tot;}bool spfa(int &flow,int &cost){for (int i=s;i<=t;i++)d[i]=inf,inq[i]=0;q.push(s);inq[s]=1,d[s]=0,a[s]=inf,p[s]=0;while (!q.empty()){int x=q.front();q.pop();inq[x]=0;for (int i=h[x];i;i=E[i].ne){edge e=E[i];if (d[e.to]>d[x]+e.cost&&e.cap>e.flow){d[e.to]=d[x]+e.cost;p[e.to]=i;a[e.to]=min(a[x],e.cap-e.flow);if (!inq[e.to])q.push(e.to),inq[e.to]=1;}}}if (d[t]==inf) return false;flow+=a[t];cost+=(a[t]*d[t]);int x=t;while (x!=s){int y=p[x];E[y].flow+=a[n];E[y^1].flow-=a[n];x=E[y].from;}return true;}void mincost(){int flow=0,cost=0;while (spfa(flow,cost));printf("%d %d\n",flow,cost);}int main(){scanf("%d%d",&n,&m);for (int i=1;i<=m;i++){int x,y,c;scanf("%d%d%d",&x,&y,&c);Addedge(x+n,y,1,c);}for (int i=2;i<n;i++)Addedge(i,i+n,1,0);t=2*n+1;Addedge(1,n+1,inf,0),Addedge(n,n+n,inf,0);Addedge(s,1,inf,0),Addedge(2*n,t,inf,0);mincost();return 0;}

人生重要的不是所站的位置，而是所朝的方向