2306 晨跑
2009年省队选拔赛山东
时间限制: 1 s
空间限制: 256000 KB
题目等级 : 大师 Master
题目描述 Description
Elaxia最近迷恋上了空手道，他为自己设定了一套健身计划，比如俯卧撑、仰卧起坐等等，不过到目前为止，他坚持下来的只有晨跑。
现在给出一张学校附近的地图，这张地图中包含N个十字路口和M条街道，Elaxia只能从一个十字路口跑向另外一个十字路口，街道之间只在十字路口处相交。Elaxia每天从寝室出发跑到学校，保证寝室编号为1，学校编号为N。
Elaxia的晨跑计划是按周期（包含若干天）进行的，由于他不喜欢走重复的路线，所以在一个周期内，每天的晨跑路线都不会相交（在十字路口处），寝室和学校不算十字路口。Elaxia耐力不太好，他希望在一个周期内跑的路程尽量短，但是又希望训练周期包含的天数尽量长。
除了练空手道，Elaxia其他时间都花在了学习和找MM上面，所有他想请你帮忙为他设计一套满足他要求的晨跑计划。
输入描述 Input Description
第一行：两个数N,M。表示十字路口数和街道数。
接下来M行，每行3个数a,b,c，表示路口a和路口b之间有条长度为c的街道（单向）。
输出描述 Output Description
两个数，第一个数为最长周期的天数，第二个数为满足最长天数的条件下最短的路程长度。
样例输入 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
数据范围及提示 Data Size & Hint
对于30%的数据，N ≤ 20，M ≤ 120。
对于100%的数据，N ≤ 200，M ≤ 20000。
题解：
裸的最大流和最小费用最大流。
代码：
#include<cstdio>
#include<queue>
#include<algorithm>
#include<iostream>
#include<cstring>
#define maxn 1010
#define S 1
#define T n*2
#define INF 0x7fffffff using namespace std; int head[maxn],n,m,dis[maxn],inq[maxn],from[maxn],cnt=,ans; struct ss
{
int to;
int next;
int c;
int w;
int from;
int edge;
}e[<<]; void add(int u,int v,int c,int w)
{
e[++cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt;
e[cnt].c=c;
e[cnt].w=w;
e[cnt].from=u;
e[cnt].edge=c;
} void insert(int u,int v,int c,int w)
{
add(u,v,c,w);
add(v,u,,-w);
} bool bfs()
{
for (int i=;i<=T;i++) dis[i]=INF;
dis[S]=;
queue<int>que;
que.push(S);
while (!que.empty())
{
int now=que.front();
que.pop();
for (int i=head[now];i;i=e[i].next)
if (e[i].edge&&dis[e[i].to]>dis[now]+)
{
dis[e[i].to]=dis[now]+;
que.push(e[i].to);
if (e[i].to==T) return ;
}
}
return ;
} int dfs(int x,int inf)
{
if (x==T) return inf;
int rest=inf;
for (int i=head[x];i&&rest;i=e[i].next)
if (e[i].edge&&dis[e[i].to]==dis[x]+)
{
int now=dfs(e[i].to,min(e[i].edge,inf));
if (!now) dis[now]=;
e[i].edge-=now;
e[i^].edge+=now;
rest-=now;
}
return inf-rest;
} bool spfa()
{
for (int i=;i<=T;i++) dis[i]=INF;
queue<int>que;
que.push(S);
inq[S]=;
dis[S]=;
while (!que.empty())
{
int now=que.front();
que.pop();
inq[now]=;
for (int i=head[now];i;i=e[i].next)
if (e[i].c&&dis[e[i].to]>dis[now]+e[i].w)
{
dis[e[i].to]=dis[now]+e[i].w;
from[e[i].to]=i;
if (!inq[e[i].to]) que.push((e[i].to)),inq[e[i].to]=;
}
}
if (dis[T]!=INF) return ;
else return ;
} void mcf()
{
int x=INF;
for (int i=from[T];i;i=from[e[i].from])
x=min(x,e[i].c);
for (int i=from[T];i;i=from[e[i].from])
{
ans+=e[i].w*x;
e[i].c-=x;
e[i^].c+=x;
}
}
void solve()
{
int ansn=;
while (bfs()) ansn+=dfs(S,INF);
printf("%d ",ansn);
while (spfa()) mcf();
printf("%d\n",ans);
} int main()
{
scanf("%d%d",&n,&m);
insert(S,S+n,INF,);
for (int i=;i<n;i++)
insert(i,i+n,,);
insert(n,n<<,INF,);
for (int i=;i<=m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
insert(u+n,v,,w);
}
solve();
return ;
}