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()?當我沒說）
[cpp]
#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;
}
#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;
}
