bzoj 1266: [AHOI2006]上学路线route

.

题意：无向图。1. 1到n的最短路。2. 最少付出多少代价删边可以使最短路边长。
题解：最短路+最小割。
代码：

#include<bits/stdc++.h>
#define pa pair<int,int>
using namespace std;

int n,m,num=1,fst[510],dis[510],h[510],s,t,ans=0;
struct edge
{
    int x,y,c,d,n;
}e[500000];
vector<int>pre[510];
bool v[510];

void ins(int x,int y,int c,int d)
{
    e[++num]={x,y,c,d,fst[x]};
    fst[x]=num;
}
inline void dijkstra()
{
    for(int i=1;i<=n;i++)
    {
        v[i]=0;
        dis[i]=2147483647;
    }
    dis[s]=0;
    static priority_queue<pa,vector<pa>,greater<pa> >q;
    q.push(make_pair(0,s));
    while(!q.empty())
    {
//        print(q);
        int x=q.top().second;
        q.pop();
        if(v[x])
        continue;
        v[x]=1;
        for(int i=fst[x];i;i=e[i].n)
        {
            int y=e[i].y;
            if(dis[y]==dis[x]+e[i].c)
            {
                pre[y].push_back(i);
            }
            else if(dis[y]>dis[x]+e[i].c)
            {
                pre[y].clear();
                pre[y].push_back(i);
                dis[y]=dis[x]+e[i].c;
                q.push(make_pair(dis[y],y));
            }
        }
    }
}
void dfs(int x)
{
    if(v[x])
    return;
    v[x]=1;
    for(int i=0;i<pre[x].size();i++)
    {
        ins(e[pre[x][i]].x,e[pre[x][i]].y,0,e[pre[x][i]].d);
        ins(e[pre[x][i]].y,e[pre[x][i]].x,0,0);
        dfs(e[pre[x][i]].x);
    }
}
bool bh()
{
    static queue<int>q;
    for(int i=1;i<=n;i++)
    h[i]=0;
    q.push(s);
    h[1]=1;
    while(!q.empty())
    {
        int x=q.front();
        for(int i=fst[x];i;i=e[i].n)
        {
            int y=e[i].y;
            if(!h[y]&&e[i].d)
            {
                h[y]=h[x]+1;
                q.push(y);
            }
        }
        q.pop();
    }/*
    for(int i=1;i<=n;i++)
    printf("%d ",h[i]);
    puts("");*/
    return h[t];
}
int fd(int x,int f)
{
    if(x==t)
    return f;
    int s=0;
    for(int i=fst[x];i;i=e[i].n)
    {
        int y=e[i].y;
        if(s<f&&h[y]==h[x]+1&&e[i].d)
        {
            int t=fd(y,min(f-s,e[i].d));
            s+=t;
            e[i].d-=t;
            e[i^1].d+=t;
        }
    }
    if(s==0)
    h[x]=0;
    return s;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
    {
        int x,y,c,d;
        scanf("%d%d%d%d",&x,&y,&c,&d);
        ins(x,y,c,d);
        ins(y,x,c,d);
    }
    s=1;
    t=n;
    dijkstra();
    for(int i=1;i<=n;i++)
    fst[i]=v[i]=0;
    int on=num;
    dfs(n);/*
    for(int i=on+1;i<=num;i++)
    printf("%d %d %d\n",e[i].x,e[i].y,e[i].d);*/
    while(bh())
    ans+=fd(s,1<<30);
    printf("%d\n%d",dis[t],ans);
}