Beyond the Void
BYVoid
AHOI 上學路線
本文正體字版由OpenCC轉換

題目要求是刪除權值之和最少的一些邊,使得從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

相關日誌