BZOJ 1266 [AHOI2006]上學路線route

題目描述

可可和卡卡家住合肥市的東郊，每天上學他們都要轉車多次才能到達市區西端的學校。直到有一天他們兩人參加了學校的資訊學奧林匹克競賽小組才發現每天上學的乘車路線不一定是最優的。 可可：“很可能我們在上學的路途上浪費了大量的時間，讓我們寫一個程式來計算上學需要的最少時間吧！” 合肥市一共設有N個公共汽車站，不妨将它們編号為1…N的自然數，并認為可可和卡卡家住在1号汽車站附近，而他們學校在N号汽車站。市内有M條直達汽車路線，執行第i條路線的公共汽車往返于站點pi和qi之間，從起點到終點需要花費的時間為ti。(1<=i<=M, 1<=pi, qi<=N) 兩個人坐在電腦前，根據上面的資訊很快就程式設計算出了最優的乘車方案。然而可可忽然有了一個鬼點子，他想趁卡卡不備，在卡卡的輸入資料中删去一些路線，進而讓卡卡的程式得出的答案大于實際的最短時間。而對于每一條路線i事實上都有一個代價ci：删去路線的ci越大卡卡就越容易發現這個玩笑，可可想知道什麼樣的删除方案可以達到他的目的而讓被删除的公共汽車路線ci之和最小。 [任務] 編寫一個程式：  從輸入檔案中讀取合肥市公交路線的資訊；  計算出實際上可可和卡卡上學需要花費的最少時間；  幫助可可設計一個方案，删除輸入資訊中的一些公交路線，使得删除後從家到學校需要的最少時間變大，而被删除路線的ci和最小；向輸出檔案輸出答案。

輸入

輸入檔案中第一行有兩個正整數N和M，分别表示合肥市公共汽車站和公交汽車路線的個數。以下M行，每行（第i行，總第(i+1)行）用四個正整數描述第i條路線：pi, qi, ti, ci；具體含義見上文描述。

輸出

輸出檔案最多有兩行。 第一行中僅有一個整數，表示從可可和卡卡家到學校需要的最短時間。 第二行輸出一個整數C,表示Ci之和

樣例輸入

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

樣例輸出

2

5

提示

2<=N<=500, 1<=M<=124 750, 1<=ti, ci<=10 000

合肥市的公交網絡十分發達，你可以認為任意兩個車站間都可以通過直達或轉車互相到達，當然如果在你提供的删除方案中，家和學校無法互相到達，那麼則認為上學需要的最短為正無窮大：這顯然是一個合法的方案。

吐槽

　　這題各種單向邊雙向邊變來變去，一會單向，一會雙向，一會又單向添加兩次，各種亂七八糟的，把我自己繞暈了。隻是粗淺地搞懂原理，卻沒真正了解題目意思和解法真的不好啊！

解題思路

　　第一問單源最短路，才500個點，随便亂搞套各種模闆的節奏，這裡我選擇了代碼量極短的Floyd（後面求最小割即最大流時加邊比spfa更友善）。

　　然後第二問，要把所有最短路徑都切斷，那麼我們用Floyd或其他spfa什麼的跑出所有最短路構成的圖，每條邊的切割代價為c，那麼求一波這個圖的最小割，就是答案了（好像BZOJ 1002 狼抓兔子啊）。由于最小割等于最大流，是以我們在最短路圖上跑最大流算法即可，這裡我用的Dinic，蒟蒻版幾乎無優化。

源代碼

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m;
 
struct Edge_road{
    int u,v,w,c;
}g[130000];
int dis[510][510],num=1;
inline void addg(int u,int v,int w,int c)
{
    g[num++]={u,v,w,c};//不排序的前向星，隻加單向邊
    dis[u][v]=dis[v][u]=min(dis[u][v],w);//dis數組用來跑floyd，加雙向邊，有重邊則選最小邊長的一條邊
}
inline void floyd()
{
    for(int i=1;i<=n;i++) dis[i][i]=0;
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
 
struct Edge_flow{
    int next,to,flow;
}e[300010];
int cnt=2,head[510]={0};
inline void add(int u,int v,int c)
{
    e[cnt]={head[u],v,c};
    head[u]=cnt++;
    e[cnt]={head[v],u,0};
    head[v]=cnt++;
}
 
int dep[510]={0};
bool bfs()
{
    memset(dep,0,sizeof(dep));
    queue<int> q;
    dep[1]=1;
    q.push(1);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=e[i].next)
        {
            int v=e[i].to;
            if(!dep[v]&&e[i].flow)
            {
                dep[v]=dep[u]+1;
                q.push(v);
            }
        }
    }
    return dep[n]!=0;
}
 
int dfs(int u,int f)
{
    if(u==n||f==0) return f;
    int sum=0;
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(dep[v]==dep[u]+1&&e[i].flow)
        {
            int delta=dfs(v,min(f-sum,e[i].flow));
            sum+=delta;
            e[i].flow-=delta;
            e[i^1].flow+=delta;
            if(f-sum<=0) break;
        }
    }
    if(!sum) dep[u]=-1;
    return sum;
}
int main()
{
    scanf("%d%d",&n,&m);
    memset(dis,0x3f,sizeof(dis));
    memset(g,-1,sizeof(-1));
    for(int i=1,u,v,w,c;i<=m;i++)
    {
        scanf("%d%d%d%d",&u,&v,&w,&c);
        addg(u,v,w,c);
    }
    floyd();
    printf("%d\n",dis[1][n]);
    for(int i=1;i<=m;i++)
    {
        int u=g[i].u,v=g[i].v,w=g[i].w,c=g[i].c;
        if(dis[1][u]+w+dis[v][n]==dis[1][n]) add(u,v,c);
        if(dis[1][v]+w+dis[u][n]==dis[1][n]) add(v,u,c);//如果這條邊在最短路上，就加到最短路圖中
    }
    int ans=0;
    while(bfs())
    {
        while(int temp=dfs(1,0x7fffffff))
            ans+=temp;
    }
    printf("%d\n",ans);
     
    return 0;
}