1877: [SDOI2009]晨跑
Description
Elaxia最近迷恋上了空手道，他为自己设定了一套健身计划，比如俯卧撑、仰卧起坐等 等，不过到目前为止，他
坚持下来的只有晨跑。 现在给出一张学校附近的地图，这张地图中包含N个十字路口和M条街道，Elaxia只能从 一
个十字路口跑向另外一个十字路口，街道之间只在十字路口处相交。Elaxia每天从寝室出发 跑到学校，保证寝室
编号为1，学校编号为N。 Elaxia的晨跑计划是按周期（包含若干天）进行的，由于他不喜欢走重复的路线，所以
在一个周期内，每天的晨跑路线都不会相交（在十字路口处），寝室和学校不算十字路 口。Elaxia耐力不太好，
他希望在一个周期内跑的路程尽量短，但是又希望训练周期包含的天 数尽量长。 除了练空手道，Elaxia其他时间
都花在了学习和找MM上面，所有他想请你帮忙为他设计 一套满足他要求的晨跑计划。
Input
第一行：两个数N,M。表示十字路口数和街道数。
接下来M行，每行3个数a,b,c，表示路口a和路口b之间有条长度为c的街道（单向）。
N ≤ 200，M ≤ 20000。
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
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
题解：对于每个点i，新建两个点i+n/i+2*n,向i连一条流量为1，费用为0的边，保证每个交叉点只经过一次，跑一边最小费用最大流，对应的数组大小什么的也要变大。*/#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<queue>
#define inf 2147483647
#define nn 610
#define mm 50010
#define lo long long
using namespace std;
bool vis[nn];
int nxt[mm],fir[nn],to[mm],w[mm],flow[mm],dis[nn],ansc=0,e=1,n,m,S,T; //之前s和其他变量重名了，所以改成了大写
int getc()
{
int ans=0,f=1;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) {ans=ans*10+ch-'0';ch=getchar();}
return ans*f;
}
void add(int a,int b,int c,int d)
{
nxt[++e]=fir[a];fir[a]=e;to[e]=b;w[e]=c;flow[e]=d;
nxt[++e]=fir[b];fir[b]=e;to[e]=a;w[e]=-c;flow[e]=0; //我看到是单向边，就只建了一条边
}
inline bool spfa()
{
int o;
deque<int> q;
q.push_back(S);
fill(vis,vis+3*n+1,0); //加了新点，大小要变
fill(dis,dis+3*n+1,inf);
dis[S]=0;vis[S]=1;
while(!q.empty())
{
o=q.front();q.pop_front();
for(int i=fir[o];i>1;i=nxt[i]) //由于边是从2开始的，所以判断条件要改成i>1
if(flow[i]&&dis[o]+w[i]<dis[to[i]])
{
dis[to[i]]=dis[o]+w[i];
if(!vis[to[i]])
{
vis[to[i]]=1;
if(!q.empty()&&dis[to[i]]<dis[q.front()])
q.push_front(to[i]);
else q.push_back(to[i]);
}
}
vis[o]=0;
}
return dis[T]!=inf;
}
inline int mcmf(int now,int f)
{
if(!f||now==T) {vis[now]=1;return f;} //写成了return 0
int newflow,newans=0,minf;
vis[now]=1;
for(int i=fir[now];i;i=nxt[i])
if(!vis[to[i]]&&dis[now]+w[i]==dis[to[i]]&&flow[i])
{
minf=min(f,flow[i]);
newflow=mcmf(to[i],minf); //流量要和flow[i]取min
ansc+=newflow*w[i];
f-=newflow;
flow[i]-=newflow;
flow[i^1]+=newflow;
newans+=newflow;
if(!f) break;
}
if(!newans) dis[now]=inf;
return newans;
}
int u,v,x,f,ansf;
int main()
{
n=getc();m=getc();
S=1;T=n; //不要忘记了
for(int i=1;i<=m;i++)
{
u=getc();v=getc();x=getc();
u=u==1? u:u+2*n;v=v==n? v:v+n;
if(u==1&&v==n)
add(u,v,x,1);
else
add(u,v,x,inf);
}
for(int i=2;i<n;i++)
{
add(i+n,i,0,1);
add(i,i+n*2,0,1);
}
while(spfa())
{
vis[T]=1;
while(vis[T]){
memset(vis,0,sizeof vis);
ansf+=mcmf(S,1e9);
}
}
printf("%d %d",ansf,ansc);
return 0;
}