上学路线(递归sap-不完全)

Posted on by
内容目录

Problem 2 上学路线(route.cpp/c/pas)

【题目描述】

可可和卡卡家住马赛克市的东郊，每天上学他们都要转车多次才能到达市区西端的学校。直到有一天他们两人参加了学校的信息学奥林匹克竞赛小组才发现每天上学的乘车路线不一定是最优的。

马赛克市一共设有N个公交车站，不妨将它们编号为1…N的自然数，并认为可可和卡卡家住在1号汽车站附近，而他们学校在N号汽车站。市内有M条直达汽车路线，执行第i条路线的公交车往返于站点pi和qi之间，从起点到终点需要花费的时间为ti。(1<=i<=M, 1<=pi, qi<=N)

两个人坐在电脑前，根据上面的信息很快就编程算出了最优的乘车方案。然而可可忽然有了一个鬼点子，他想趁卡卡不备，在卡卡的输入数据中删去一些路线，从而让卡卡的程序得出的答案大于实际的最短时间。而对于每一条路线i事实上都有一个代价ci：删去路线的ci越大卡卡就越容易发现这个玩笑，可可想知道什么样的删除方案可以达到他的目的而让被删除的公交车路线ci之和最小。

马赛克市的公交网络十分发达，你可以认为任意两个车站间都可以通过直达或转车互相到达，当然如果在你提供的删除方案中，家和学校无法互相到达，那么则认为上学需要的最短为正无穷大：这显然是一个合法的方案。

 

【输入格式】

输入文件中第一行有两个正整数N和M，分别表示马赛克市公交车站和公交汽车路线的个数。以下M行，每行（第i行，总第(i+1)行）用四个正整数（之间由一个空格隔开）描述第i条路线：pi, qi, ti, ci；具体含义见上文描述。

【输出格式】

输出文件最多有两行。 第一行中仅有一个整数，表示从可可和卡卡家到学校需要的最短时间。第二行输出一个整数C,表示Ci之和

【样例输入】

6 7

1 21 3

2 61 5

1 31 1

3 41 1

4 61 1

5 61 2

1 51 4

【样例输出】

2

5

【数据范围】

   

2<=N<=500,1<=M<=124 750, 1<=ti, ci<=10 000

 

这题我用的是递归sap()，谁知道狂Wa。

大家用递归sap的时候想必经常会莫名NTR。

结论://dfs_sap()的Z正确性目前有待考证。。。

根据我的研究，经验总结如下：

1.退出条件：

-PS：有可能某次增广flow=0，但是改距离标号可以继续flow

-PS：有时候无限增广，输答案能看出上面的错误

2.修改距离标号：

-PS：距离标号最好直接+1，minj等手段极有可能造成≈没有距离标号优化的状况

3.dfs时的flow

-PS：一定要提前return，要不然改距离标号a~

4.重构图:

-PS：这样是质的差别，递归不卡时间？

5.唯一重点：

PS：实在不行时，去掉距离标号优化！另可T到死，不能WA到爆

6.用递归sap唯一的好处是省事……（什么你1分钟BFS_sap()?当我没说）

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<functional>
#define MAXN (500+10)
#define MAXM (124750+10)
#define MAXCi (10000+10)
#define INF (2139062143)
#define For(i,n) for(int i=1;i<=n;i++)
#define Forp(p,u) for (int p=pre[u];p;p=next[p])
using namespace std;
int n,m,edge[2*MAXM],weight[2*MAXM],c[2*MAXM],next[2*MAXM],pre[MAXN],size=1;
void addedge(int u,int v,int w,int w2)
{
	edge[++size]=v;
	weight[size]=w;
	c[size]=w2;
	next[size]=pre[u];
	pre[u]=size;
}
int d[MAXN],q[MAXN*8];
void spfa()
{
	memset(d,127,sizeof(d));
	d[1]=0;
	int head=1,tail=1;q[1]=1;
	while (head<=tail)
	{
		int &u=q[head];
		Forp(p,u)
		{
			int &v=edge[p];
			if (d[v]==INF||d[u]+weight[p]<d[v])
			{
				q[++tail]=v;d[v]=d[u]+weight[p];
			}
		}
		head++;
	}
}
int d2[MAXN],cnt[MAXN];
void spfa2()
{
	memset(d2,127,sizeof(d2));
	memset(cnt,0,sizeof(cnt));
	d2[n]=0;cnt[0]=1;
	int head=1,tail=1;q[1]=n;
	while (head<=tail)
	{
		int &u=q[head];
		Forp(p,u)
		{
			int &v=edge[p];
			if (d[u]-weight[p]!=d[v]) continue;
			if (d2[v]==INF)
			{
				q[++tail]=v;d2[v]=d2[u]+1;
				cnt[d2[v]]++;
			}
		}
		head++;
	}
}
bool sap_T=1,b[2*MAXM]={0};
int sap(int u,int flow)
{
	if (u==n) return flow;
	int tot=0,minj=INF;
	Forp(p,u)
	{
		int &v=edge[p];
	/*
		if (d2[v]==INF) continue;
		if (!(d[u]+weight[p]==d[v]||d[u]-weight[p]==d[v])) continue;
	*/
		if (!b[p]) continue;
		if (c[p]>0&&d2[u]==d2[v]+1)
		{
			int w=sap(v,min(flow-tot,c[p]));
			c[p]-=w;c[p^1]+=w;tot+=w;
			if (flow==tot) return tot;
		}else if (c[p]) minj=min(minj,d2[v]);
	}
	if (--cnt[d2[u]]==0)
		{
			d2[1]=n,sap_T=0;/*return tot;*/
		}//d2[1]=n+1;
//	if (minj^INF) cnt[d2[u]=minj+1]++;
/*	else*/ cnt[++d2[u]]++;
	return tot;
}
int main()
{
	freopen("route.in","r",stdin);
	freopen("route.out","w",stdout);
	memset(pre,0,sizeof(pre));
	scanf("%d%d",&n,&m);
	For(i,m)
	{
		int u,v,w1,w2;
		scanf("%d%d%d%d",&u,&v,&w1,&w2);
		addedge(u,v,w1,w2);
		addedge(v,u,w1,w2);
	}
	spfa();
//	for (int i=1;i<=n;i++) cout<<d[i]<<' ';cout<<endl;
	cout<<d[n]<<endl;
	int ans=0;
	spfa2();
	int de_bug_1=0;
	For(i,n)
		Forp(p,i)
		{
			if (d[i]>d[edge[p]]) c[p]=0;
		//*0
		//	if (d2[i]!=INF&&d2[edge[p]]!=INF&&c[p]) cout<<i<<' '<<edge[p]<<endl,de_bug_1++;
			if (d[i]+weight[p]==d[edge[p]]) b[p]=b[p^1]=1,/*cout<<i<<' '<<edge[p]<<endl,*/de_bug_1++;
		}
//	cout<<de_bug_1<<endl;
	b[0]=1;
	For(i,n)
		Forp(p,i)
		{
			while (next[p]&&!b[next[p]]) next[p]=next[next[p]];
		}

	while(/*sap_T*/1)
	{
		if (d2[1]>=n) break;
		int w=sap(1,INF);
	//	if (!w) break;
//		cout<<ans<<' '<<d2[1]<<endl;
		ans+=w;
	}
	cout<<ans<<endl;
	return 0;
}