【原題】 1266: [AHOI2006]上學路線route Time Limit: 3 Sec Memory Limit: 162 MB Submit: 1084 Solved: 360 [Submit][Status] Description 可可和卡卡家住合肥市的東郊，每天上學他們都要轉車多次才能到達市區西端的學校。直到有一天他們兩人參加了學校的信息學奧林匹克競賽小組才發現每天上學的乘車路線不一定是最優的。 可可：“很可能我們在上學的路途上浪費了大量的時間，讓我們寫一個程序來計算上學需要的最少時間吧！” 合肥市一共設有N個公交車站，不妨將它們編號為1…N的自然數，並認為可可和卡卡家住在1號汽車站附近，而他們學校在N號汽車站。市內有M條直達汽車路線，執行第i條路線的公交車往返於站點pi和qi之間，從起點到終點需要花費的時間為ti。(1<=i<=M, 1<=pi, qi<=N) 兩個人坐在電腦前，根據上面的信息很快就編程算出了最優的乘車方案。然而可可忽然有了一個鬼點子，他想趁卡卡不備，在卡卡的輸入數據中刪去一些路線，從而讓卡卡的程序得出的答案大於實際的最短時間。而對於每一條路線i事實上都有一個代價ci：刪去路線的ci越大卡卡就越容易發現這個玩笑，可可想知道什麼樣的刪除方案可以達到他的目的而讓被刪除的公交車路線ci之和最小。 [任務] 編寫一個程序： 從輸入文件中讀取合肥市公交路線的信息； 計算出實際上可可和卡卡上學需要花費的最少時間； 幫助可可設計一個方案，刪除輸入信息中的一些公交路線，使得刪除後從家到學校需要的最少時間變大，而被刪除路線的ci和最小；向輸出文件輸出答案。 Input 輸入文件中第一行有兩個正整數N和M，分別表示合肥市公交車站和公交汽車路線的個數。以下M行，每行（第i行，總第(i+1)行）用四個正整數描述第i條路線：pi, qi, ti, ci；具體含義見上文描述。 Output 輸出文件最多有兩行。 第一行中僅有一個整數，表示從可可和卡卡家到學校需要的最短時間。 第二行輸出一個整數C,表示Ci之和 Sample Input 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 Sample Output 2 5 HINT 2<=N<=500, 1<=M<=124 750, 1<=ti, ci<=10 000 合肥市的公交網絡十分發達，你可以認為任意兩個車站間都可以通過直達或轉車互相到達，當然如果在你提供的刪除方案中，家和學校無法互相到達，那麼則認為上學需要的最短為正無窮大：這顯然是一個合法的方案。 【分析】真是桑心！！這道題切了一個晚上，最後在RC（Red Cow）的幫助下才解決的。 第一問直接是最短路啊。第二問的意思我看了好久——要選擇刪掉一些路，使起點到終點的最短路並不是原來的最短路（就是稍微大一些，哪怕大1也可以），同時使刪掉的路的ci之和最小。 這樣就很好做了，直接把原來在最短路上的邊全部拎出來，做一遍最小割（因為可能有多條最短路）。 【注意點】信心滿滿地交上去，一直是WA！恰好這一年沒有數據，我只能死磕了。自己造了幾個數據全部正確！於是無奈地網上下了個標程，寫make_data對拍。 拍了5分鐘有一個錯誤：我的q隊列開小了。在做SPFA的時候，即使用了flag數組記錄是否在隊列中，q數組也必須要開大！！（除非用循環隊列）RC說SPFA操作的隊列最保險的應該開邊的10倍。 後來就一直沒拍出錯誤，可是交上去還是WA！盯著屏幕半天，仍然沒什麼發現！最後，RC一瞪眼：是不是有重邊？我馬上把我的鄰接矩陣上加了個+，結果A了。恰好我造的數據時去重的，怪不得拍不出錯誤。 歸納兩點：SPFA隊列要開大；注意重邊。 【代碼】 [cpp] #include<cstdio> #include<cstring> #include<algorithm> #define INF 2100000000 #define N 1005 #define M 250005 using namespace std; struct arr{int go,c,next,s;}a[M]; int map[N][N],dis[2][N],f[N],q[M*2],end[N]; bool flag[N]; int x,y,z,c,i,n,m,cnt,ans; void add(int u,int v,int s,int w) { a[++cnt].go=v;a[cnt].c=w;a[cnt].s=s;a[cnt].next=end[u]; end[u]=cnt; } void SPFA(int o,int sta) { int h=0,t=1;q[1]=sta; memset(flag,0,sizeof(flag)); dis[o][sta]=0;flag[sta]=true; while (h<t) { int now=q[++h]; for (int i=end[now];i;i=a[i].next) { int go=a[i].go; if (dis[o][now]+a[i].s<dis[o][go]) { dis[o][go]=dis[o][now]+a[i].s; if (!flag[go]) flag[go]=true,q[++t]=go; } } flag[now]=false; } } void init() { for (int i=1;i<=n;i++) for (int j=end[i];j;j=a[j].next) if (dis[0][i]+a[j].s+dis[1][a[j].go]==dis[0][n]) map[i][a[j].go]+=a[j].c; } bool bfs() { memset(f,-1,sizeof(f)); int h=0,t=1;q[1]=1;f[1]=1; while (h<t) { int now=q[++h];if (now==n) return 1; for (int i=1;i<=n;i++) if (map[now][i]&&f[i]==-1) { f[i]=f[now]+1; q[++t]=i; } } return 0; } int dinic(int sta,int sum) { if (sta==n) return sum;int os=sum; for (int i=1;(i<=n)&&os;i++) if (map[sta][i]&&f[i]==f[sta]+1) { int Min=dinic(i,min(map[sta][i],os)); map[sta][i]-=Min;map[i][sta]+=Min;os-=Min; } if (os==sum) f[sta]=-1;return sum-os; } int main() { scanf("%d%d",&n,&m); for (i=1;i<=m;i++) scanf("%d%d%d%d",&x,&y,&z,&c),add(x,y,z,c),add(y,x,z,c); memset(dis,60,sizeof(dis));SPFA(0,1);SPFA(1,n); ans=0;init(); while (bfs()) ans+=dinic(1,INF); printf("%d\n%d",dis[0][n],ans); return 0; }
