Beyond the Void
BYVoid
AHOI 上学路线

题目要求是删除权值之和最少的一些边,使得从1到N的最短路径变大。方法是求最短路径网络上的最小割集。首先求出从1到N的最短路径网络,方法是分别从1和N求单源最短路径,然后枚举每条边,如果边(a,b)满足dis(1,a) + w(a,b) + dis(b,N) = dis(1,N) ,则(a,b)是最短路径网络上的(有向)边。

接下来求从1到N的网络最大流,即可求出最小割集。由于是求任意一个最小割集,所以只需遍历一边残余网络,S集合与T集合之间的边,就是一个最小割集。

/* 
 * Problem: HAOI2008 parterre
 * Author: Guo Jiabao
 * Time: 2009.4.21 10:23
 * State: Solved
 * Memo: 最短路径 + 网络流
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=501,MAXM=124751*4,INF=0x7FFFFFF;
using namespace std;
struct edge
{
	edge *next,*op;
	int s,t,d,c,id;
}*Vr[MAXN],*V[MAXN],ES[MAXM],*P[MAXN],*Stae[MAXN];
int N,M,EC,S,T,Ecnt;
int sp[2][MAXN],Cost[MAXM],Anse[MAXM];
bool vis[MAXN];
int Lv[MAXN],Q[MAXN],Stap[MAXN],Stop;
bool dinic_bfs()
{
	int i,j,head=0,tail=-1;
	memset(Lv,-1,sizeof(Lv));
	Q[++tail]=S;
	Lv[S]=0;
	while (head<=tail)
	{
		i=Q[head++];
		for (edge *e=V[i];e;e=e->next)
		{
			if (Lv[j=e->t]==-1 && e->c)
			{
				Lv[j]=Lv[i]+1;
				Q[++tail]=j;
				if (j==T)
					return true;
			}
		}
	}
	return false;
}
int dinic_augment()
{
	int i,j,k,delta,Flow=0;
	for (i=S;i<=T;i++)
		P[i]=V[i];
	Stap[Stop=1]=S;
	while (Stop)
	{
		i=Stap[Stop];
		if (i!=T)
		{
			for (;P[i];P[i]=P[i]->next)
				if (P[i]->c && Lv[i]+1==Lv[j=P[i]->t])
					break;
			if (P[i])
			{
				Stap[++Stop]=j;
				Stae[Stop]=P[i];
			}
			else
			{
				Stop--;
				Lv[i]=-1;
			}
		}
		else
		{
			delta=INF;
			for (j=Stop;j>=2;j--)
				if (Stae[j]->c < delta)
					delta=Stae[j]->c;
			Flow+=delta;
			for (j=Stop;j>=2;j--)
			{
				Stae[j]->c-=delta;
				Stae[j]->op->c+=delta;
				if (Stae[j]->c==0)
					k=j-1;
			}
			Stop=k;
		}
	}
	return Flow;
}
int dinic()
{
	int Flow=0;
	while (dinic_bfs())
		Flow += dinic_augment();
	return Flow;
}
inline void addedge1(int a,int b,int d,int c,int id)
{
	ES[++EC].next=Vr[a];
	Vr[a]=ES+EC; Vr[a]->t=b; Vr[a]->c=c; Vr[a]->d=d;
	ES[++EC].next=Vr[b];
	Vr[b]=ES+EC; Vr[b]->t=a; Vr[b]->c=c; Vr[b]->d=d;
	Vr[a]->op=Vr[b]; Vr[b]->op=Vr[a];
	Vr[a]->s=a; Vr[b]->s=b;
	Vr[a]->id=Vr[b]->id=id;
}
inline void addedge2(int a,int b,int c,int id)
{
	ES[++EC].next=V[a];
	V[a]=ES+EC; V[a]->t=b; V[a]->c=c;
	ES[++EC].next=V[b];
	V[b]=ES+EC; V[b]->t=a; V[b]->c=0;
	V[a]->op=V[b]; V[b]->op=V[a];
	V[a]->id=V[b]->id=id;
}
void init()
{
	int i,a,b,d,c;
	freopen("routez.in","r",stdin);
	freopen("routez.out","w",stdout);
	scanf("%d%d",&N,&M);
	EC=0;
	for (i=1;i<=M;i++)
	{
		scanf("%d%d%d%d",&a,&b,&d,&c);
		addedge1(a,b,d,c,i);
	}
}
void dijkstra(int S,int *sp)
{
	int i,j,Mini;
	memset(vis,0,sizeof(vis));
	for (i=1;i<=N;i++)
		sp[i]=INF;
	sp[i=S]=0;
	for (;i;)
	{
		vis[i]=true;
		for (edge *e=Vr[i];e;e=e->next)
		{
			j=e->t;
			if (sp[i] + e->d < sp[j])
				sp[j] = sp[i]+ e->d;
		}
		i=0;Mini=INF;
		for (j=1;j<=N;j++)
			if (!vis[j] && sp[j]<Mini)
			{
				Mini=sp[j];
				i=j;
			}
	}
}
void network()
{
	int i,a,b,p=EC;
	S=1,T=N;
	Ecnt=0;
	for (i=1;i<=p;i++)
	{
		a=ES[i].s,b=ES[i].t;
		if (sp[0][a] + ES[i].d + sp[1][b] == sp[0][N])
			addedge2(a,b,ES[i].c,ES[i].id);
	}
}
int getcut()
{
	int i,j,C=0;
	dinic_bfs();
	for (i=1;i<=N;i++)
	{
		for (edge *e=V[i];e;e=e->next)
		{
			j=e->t;
			if (Lv[i]!=-1 && Lv[j]==-1)
				Anse[++C]=e->id;
		}
	}
	return C;
}
void solve()
{
	int Ans1,Ans2,Ans3;
	dijkstra(1,sp[0]);
	dijkstra(N,sp[1]);
	Ans1=sp[0][N];
	network();
	Ans3=dinic();
	Ans2=getcut();
	printf("%dn%d %dn",Ans1,Ans2,Ans3);
	for (int i=1;i<=Ans2;i++)
		printf("%dn",Anse[i]);
}
int main()
{
	init();
	solve();
	return 0;
}
<div class="MainText">
<div><strong>上学路线</strong></div>
<div>可可和卡卡家住HF市的东郊,每天上学他们都要转车多次才能到达市区西端的学校。直到有一天他们两人参加了学校的信息学奥林匹克竞赛小组才发现每天上学的乘车路线不一定是最优的。</div>
<div>可可:“很可能我们在上学的路途上浪费了大量的时间,让我们写一个程序来计算上学需要的最少时间吧!”</div>
<div>HF市一共设有 <em>N </em>个公交车站,不妨将它们编号为 1… <em>N </em>的自然数,并认为可可和卡卡家住在 1 号汽车站附近,而他们学校在 <em>N </em>号汽车站。市内有 <em>M </em>条直达汽车路线,执行第 <em>i </em>条路线的公交车 <strong>往返于 </strong>站点 <em>p </em>i 和 <em>q </em>i 之间,从起点到终点需要花费的时间为 <em>t i </em>。 (1&lt;= <em>i </em>&lt;= <em>M </em>, 1&lt;= <em>p i </em>, <em>q i </em>&lt;= <em>N </em>)</div>
<div>两个人坐在电脑前,根据上面的信息很快就编程算出了最优的乘车方案。然而可可忽然有了一个鬼点子,他想趁卡卡不备,在卡卡的输入数据中删去一些路线,从而让卡卡的程序得出的答案大于实际的最短时间。而对于每一条路线 <em>i </em>事实上都有一个代价 <em>c i </em>:删去路线的 <em>c i </em>越大卡卡就越容易发现这个玩笑,可可想知道什么样的删除方案可以达到他的目的而让被删除的公交车路线 <em>c i </em>之和最小。</div>
<div><strong><span>[ 任务 ] </span></strong></div>
<div>编写一个程序:</div>
<div>•  从输入文件中读取HF市公交路线的信息;</div>
<div>•  计算出实际上可可和卡卡上学需要花费的最少时间;</div>
<div>•  帮助可可设计一个方案,删除输入信息中的一些公交路线,使得删除后从家到学校需要的最少时间变大,而被删除路线的 <em>c i </em>和最小;</div>
<div>•  向输出文件输出答案。</div>
<div><strong><span>[ 输入格式 ] </span></strong></div>
<div>输入文件中第一行有两个正整数 <em>N </em>和 <em>M </em>,分别表示HF市公交车站和公交汽车路线的个数。以下 <em>M </em>行,每行(第 <em>i </em>行,总第 ( <em>i </em>+1) 行)用四个正整数描述第 <em>i </em>条路线: <em>p i </em>, <em>q i </em>, <em>t i </em>, <em>c i </em>;具体含义见上文描述。</div>
<div><strong><span>[ 输出格式 ] </span></strong></div>
<div>输出文件最多有两行。</div>
<div>第一行中仅有一个整数,表示从可可和卡卡家到学校需要的最短时间。</div>
<div>第二行描述你为可可制定的方案,首先有两个整数 <em>K </em>和 <em>C </em>,表示总共需要删除 <em>K </em>条路线,它们的 <em>c i </em>之和为 <em>C </em>最小;</div>
<div>接着有 <em>K </em>行,每行1个 1… <em>N </em>的正整数: <em>d </em>1 , <em>d </em>2 , …, <em>d K </em>,表示需要删除的路线编号,即输入文件中顺数的编号。<strong>如果有多解,输出任意一个。</strong></div>
<div><strong><span>[ 输入样例 ] </span></strong></div>
<div>6 7
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</div>
<div><strong><span>[ 输出样例 ] </span></strong></div>
<div>2
2 5</div>
<div>16</div>
<div><strong><span>[ 数据约束 ] </span></strong></div>
<div>2&lt;= <em>N </em>&lt;=500, 1&lt;= <em>M </em>&lt;=124 750, 1&lt;= <em>t i </em>, <em>c i </em>&lt;=10 000</div>
<div>HF市的公交网络十分发达,你可以认为任意两个车站间都可以通过直达或转车互相到达,当然如果在你提供的删除方案中,家和学校无法互相到达,那么则认为上学需要的最短为正无穷大:这显然是一个合法的方案。</div>
</div>

上次修改时间 2017-05-22

相关日志