转载请注明：http://blog.csdn.net/jiangshibiao/article/details/23989499
【原题】
1266: [AHOI2006]上学路线route
Time Limit: 3 Sec Memory Limit: 162 MB
Submit: 1084 Solved: 360
[Submit][Status]
Description
1<=pi, qi<=N) 两个人坐在电脑前，根据上面的信息很快就编程算出了最优的乘车方案。然而可可忽然有了一个鬼点子，他想趁卡卡不备，在卡卡的输入数据中删去一些路线，从而让卡卡的程序得出的答案大于实际的最短时间。而对于每一条路线i事实上都有一个代价ci：删去路线的ci越大卡卡就越容易发现这个玩笑，可可想知道什么样的删除方案可以达到他的目的而让被删除的公交车路线ci之和最小。 [任务] 编写一个程序： 从输入文件中读取合肥市公交路线的信息； 计算出实际上可可和卡卡上学需要花费的最少时间； 帮助可可设计一个方案，删除输入信息中的一些公交路线，使得删除后从家到学校需要的最少时间变大，而被删除路线的ci和最小；向输出文件输出答案。
Input
Output
Sample Input
1 2 1 3
2 6 1 5
1 3 1 1
3 4 1 1
4 6 1 1
5 6 1 2
1 5 1 4
Sample Output
5
HINT
2<=N<=500, 1<=M<=124 750, 1<=ti, ci<=10 000
合肥市的公交网络十分发达，你可以认为任意两个车站间都可以通过直达或转车互相到达，当然如果在你提供的删除方案中，家和学校无法互相到达，那么则认为上学需要的最短为正无穷大：这显然是一个合法的方案。
【分析】真是桑心！！这道题切了一个晚上，最后在RC（Red Cow）的帮助下才解决的。
第一问直接是最短路啊。第二问的意思我看了好久——要选择删掉一些路，使起点到终点的最短路并不是原来的最短路（就是稍微大一些，哪怕大1也可以），同时使删掉的路的ci之和最小。
这样就很好做了，直接把原来在最短路上的边全部拎出来，做一遍最小割（因为可能有多条最短路）。
【注意点】信心满满地交上去，一直是WA！恰好这一年没有数据，我只能死磕了。自己造了几个数据全部正确！于是无奈地网上下了个标程，写make_data对拍。
拍了5分钟有一个错误：我的q队列开小了。在做SPFA的时候，即使用了flag数组记录是否在队列中，q数组也必须要开大！！（除非用循环队列）RC说SPFA操作的队列最保险的应该开边的10倍。
后来就一直没拍出错误，可是交上去还是WA！盯着屏幕半天，仍然没什么发现！最后，RC一瞪眼：是不是有重边？我马上把我的邻接矩阵上加了个+，结果A了。恰好我造的数据时去重的，怪不得拍不出错误。
归纳两点：SPFA队列要开大；注意重边。
【代码】
#include<cstdio>
#include<cstring>
#include<algorithm>
#define INF 2100000000
#define N 1005
#define M 250005
using namespace std;
struct arr{int go,c,next,s;}a[M];
int map[N][N],dis[2][N],f[N],q[M*2],end[N];
bool flag[N];
int x,y,z,c,i,n,m,cnt,ans;
void add(int u,int v,int s,int w)
{
a[++cnt].go=v;a[cnt].c=w;a[cnt].s=s;a[cnt].next=end[u];
end[u]=cnt;
}
void SPFA(int o,int sta)
{
int h=0,t=1;q[1]=sta;
memset(flag,0,sizeof(flag));
dis[o][sta]=0;flag[sta]=true;
while (h<t)
{
int now=q[++h];
for (int i=end[now];i;i=a[i].next)
{
int go=a[i].go;
if (dis[o][now]+a[i].s<dis[o][go])
{
dis[o][go]=dis[o][now]+a[i].s;
if (!flag[go]) flag[go]=true,q[++t]=go;
}
}
flag[now]=false;
}
}
void init()
{
for (int i=1;i<=n;i++)
for (int j=end[i];j;j=a[j].next)
if (dis[0][i]+a[j].s+dis[1][a[j].go]==dis[0][n])
map[i][a[j].go]+=a[j].c;
}
bool bfs()
{
memset(f,-1,sizeof(f));
int h=0,t=1;q[1]=1;f[1]=1;
while (h<t)
{
int now=q[++h];if (now==n) return 1;
for (int i=1;i<=n;i++)
if (map[now][i]&&f[i]==-1)
{
f[i]=f[now]+1;
q[++t]=i;
}
}
return 0;
}
int dinic(int sta,int sum)
{
if (sta==n) return sum;int os=sum;
for (int i=1;(i<=n)&&os;i++)
if (map[sta][i]&&f[i]==f[sta]+1)
{
int Min=dinic(i,min(map[sta][i],os));
map[sta][i]-=Min;map[i][sta]+=Min;os-=Min;
}
if (os==sum) f[sta]=-1;return sum-os;
}
int main()
{
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++)
scanf("%d%d%d%d",&x,&y,&z,&c),add(x,y,z,c),add(y,x,z,c);
memset(dis,60,sizeof(dis));SPFA(0,1);SPFA(1,n);
ans=0;init();
while (bfs())
ans+=dinic(1,INF);
printf("%d\n%d",dis[0][n],ans);
return 0;
}