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。 【题解】【这道题，看看输出“最长周期的天数”和“满足最长天数的条件下最短的路程长度”，哎呀，这不显然费用流吗？！】 【因为，每个路口只能经过一次，所以拆点拆点！另设一个超级源点和一个超级汇点，然后将原图中的点全部拆点，流量为1，费用为0（注意：起点和终点拆点后两点连线的流量为INF），然后连边时起点的出点连终点的入点，流量为1，费用为路径长度。 然后跑费用流就行了】#include#include #include #include #include #define INF 0x7fffffffusing namespace std;int a[80010],next[80010],p[410],cost[80010],remain[80010],tot;int dis[410],last[410];int n,m,S,T,mincost,maxflow;bool b[410];inline void add(int x,int y,int flow,int val){ a[tot]=y; next[tot]=p[x]; p[x]=tot; remain[tot]=flow; cost[tot]=val; tot++; a[tot]=x; next[tot]=p[y]; p[y]=tot; remain[tot]=0; cost[tot]=-val; tot++; }inline int addflow(int s,int t){ int now=t,ans=0x7fffffff; while (now!=s) { ans=min(ans,remain[last[now]]); now=a[last[now]^1]; } now=t; while (now!=s) { remain[last[now]]-=ans; remain[last[now]^1]+=ans; now=a[last[now]^1]; } return ans;}inline bool spfa(int s,int t){ int i; queue que; memset(dis,127/3,sizeof(dis)); memset(b,true,sizeof(b)); i=dis[0]; que.push(s); b[s]=false; dis[s]=0; while (!que.empty()) { int u,v; u=que.front(); que.pop(); v=p[u]; b[u]=true; while (v!=-1) { if (remain[v]&&dis[a[v]]>dis[u]+cost[v]) { dis[a[v]]=dis[u]+cost[v]; last[a[v]]=v; if (b[a[v]]) { que.push(a[v]); b[a[v]]=false; } } v=next[v]; } } if (dis[t]>=i) return false; int sum=addflow(s,t); maxflow+=sum; mincost+=dis[t]*sum; return true; }int main(){ int i,j; memset(p,-1,sizeof(p)); memset(next,-1,sizeof(next)); scanf("%d%d",&n,&m); T=n*2+1; add(S,1,INF,0); add(n*2,T,INF,0); add(1,1+n,INF,0); add(n,n+n,INF,0); for (i=2;i