通学路(再帰sap-不完全)
4871 ワード
Problem 2通学路(route.cpp/c/pas)
【タイトル説明】
ココとカカの家はモザイク市の東郊外に住んでいて、毎日学校に通っていて、市街地の西端の学校に着くには何度も乗り換えなければなりません.ある日、彼ら2人は学校の情報学オリンピック競技グループに参加して、毎日学校に通う乗車ルートが必ずしも最適ではないことに気づいた.
モザイク市には全部でNつのバス停があります.それらの番号を1...Nの自然数にして、ココアとカカの家は1番のバス停の近くに住んでいますが、彼らの学校はN番のバス停にあります.市内にはM本の直通バス路線があり、i本目の路線を運行するバスは駅piとqiの間を往復し、起点から終点までかかる時間はtiである.(1<=i<=M, 1<=pi, qi<=N)
二人はパソコンの前に座って、上の情報に基づいてすぐにプログラミングして最適な乗車案を算出しました.しかし、カカは突然、カカの不備に乗じて、カカの入力データの中でいくつかのルートを削除し、カカのプログラムの答えを実際の最短時間より大きくしようとした鬼のアイデアがあった.すべてのルートiに対して事実上すべて1つの代価ciがあります:ルートを削除するciは大きいカカほどこの冗談を発見しやすくて、ココアはどんな削除案が彼の目的を達成することができて削除されたバスのルートciの和を最小にすることができることを知りたいです.
モザイク市のバスネットワークは非常に発達しており、任意の2つの駅間で直通や乗り換えで互いに到着できると考えられています.もちろん、あなたが提供した削除案の中で、家と学校が互いに到着できない場合は、学校に必要な最短は無限大だと考えられています.これは明らかに合法的な案です.
【入力形式】
入力ファイルの最初の行には、モザイク市のバス停とバス路線の個数をそれぞれ表す正の整数NとMが2つあります.以下のM行は、各行(i行目、総(i+1)行目)が4つの正の整数(間が1つのスペースで区切られている)でi番目のルートを記述する.pi,qi,ti,ci;具体的な意味は前述のとおりである.
【出力形式】
出力ファイルは最大2行です.最初の行には整数が1つしかなく、ココアとカカの家から学校までの最短時間を表しています.2行目は、Ciの和を表す整数Cを出力する
【サンプル入力】
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を使う唯一のメリットは手間を省くことです......(BFS_sap()?私が言わなかったとき)
【タイトル説明】
ココとカカの家はモザイク市の東郊外に住んでいて、毎日学校に通っていて、市街地の西端の学校に着くには何度も乗り換えなければなりません.ある日、彼ら2人は学校の情報学オリンピック競技グループに参加して、毎日学校に通う乗車ルートが必ずしも最適ではないことに気づいた.
モザイク市には全部でNつのバス停があります.それらの番号を1...Nの自然数にして、ココアとカカの家は1番のバス停の近くに住んでいますが、彼らの学校はN番のバス停にあります.市内にはM本の直通バス路線があり、i本目の路線を運行するバスは駅piとqiの間を往復し、起点から終点までかかる時間はtiである.(1<=i<=M, 1<=pi, qi<=N)
二人はパソコンの前に座って、上の情報に基づいてすぐにプログラミングして最適な乗車案を算出しました.しかし、カカは突然、カカの不備に乗じて、カカの入力データの中でいくつかのルートを削除し、カカのプログラムの答えを実際の最短時間より大きくしようとした鬼のアイデアがあった.すべてのルートiに対して事実上すべて1つの代価ciがあります:ルートを削除するciは大きいカカほどこの冗談を発見しやすくて、ココアはどんな削除案が彼の目的を達成することができて削除されたバスのルートciの和を最小にすることができることを知りたいです.
モザイク市のバスネットワークは非常に発達しており、任意の2つの駅間で直通や乗り換えで互いに到着できると考えられています.もちろん、あなたが提供した削除案の中で、家と学校が互いに到着できない場合は、学校に必要な最短は無限大だと考えられています.これは明らかに合法的な案です.
【入力形式】
入力ファイルの最初の行には、モザイク市のバス停とバス路線の個数をそれぞれ表す正の整数NとMが2つあります.以下のM行は、各行(i行目、総(i+1)行目)が4つの正の整数(間が1つのスペースで区切られている)でi番目のルートを記述する.pi,qi,ti,ci;具体的な意味は前述のとおりである.
【出力形式】
出力ファイルは最大2行です.最初の行には整数が1つしかなく、ココアとカカの家から学校までの最短時間を表しています.2行目は、Ciの和を表す整数Cを出力する
【サンプル入力】
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を使う唯一のメリットは手間を省くことです......(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;
}