[AHOI2008]上学路线（最短路+最小割）

此题第一问最短路即可。主要是第二问。

第二问求最小的删除边的方案使得1到n的最短路变大。

最小的删除让我们想到了最小割。

然而最小割是使得1到n不连通。

于是我们把最短路图抽出来跑最小割。

一条边（x，v）当dis[x]+val[i]==dis[v]时说明这是最短路图中的一条边。

#include<bits/stdc++.h>
#define LL long long
#define N 200003
#define M 125000
#define INF 2100000000
using namespace std;
int read()
{
    int x=0,f=1;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    return x*f;
}
struct EDEG{
    int nextt,to,t,c,me;
}w[M*2],w2[M*2];
int head[N],head2[N],cur[N];
int vis[N],dis[N];
struct qnode{
    int v,c;
    qnode(int _v=0,int _c=0):v(_v),c(_c){}
    bool operator <(const qnode &r)const
    {
        return r.c<c;
    }
};
int n,m;
int tot=0,tot2=1;
void add(int a,int b,int t,int c)
{
    tot++;
    w[tot].nextt=head[a];
    w[tot].me=a;
    w[tot].t=t;
    w[tot].c=c;
    w[tot].to=b;
    head[a]=tot;
}
void add2(int a,int b,int c)
{
    tot2++;
    w2[tot2].nextt=head2[a];
    w2[tot2].c=c;
    w2[tot2].to=b;
    head2[a]=tot2;
}
priority_queue<qnode>q;
void dij()//处理第一问 
{
    while(!q.empty())q.pop();
    for(int i=1;i<=n;++i)vis[i]=0,dis[i]=INF;
    dis[1]=0;
    q.push(qnode(1,0));
    while(!q.empty())
    {
        int x=q.top().v;q.pop();
        if(vis[x])continue;
        vis[x]=1;
        for(int i=head[x];i;i=w[i].nextt)
        {
            int v=w[i].to;
            if(!vis[v]&&dis[x]+w[i].t<dis[v])
            {
                dis[v]=dis[x]+w[i].t;
                q.push(qnode(v,dis[v]));
            }
        }
    }
}
queue<int>qq;
bool bfs()
{
    memset(dis,0,sizeof(dis));//这里就将就用dis数组不再另开一个
    while(!qq.empty())qq.pop();
    qq.push(1);dis[1]=1;
    while(!qq.empty())
    {
        int x=qq.front();qq.pop();
        for(int i=head2[x];i;i=w2[i].nextt)
        {
            int v=w2[i].to;
            if(w2[i].c&&!dis[v])
            {
                qq.push(v);
                dis[v]=dis[x]+1;
                if(v==n)return 1;
            }
        }
    }
    return 0;
}
int dinic(int x,int flow)
{
    if(x==n)return flow;
    int rest=0;
    for(int &i=cur[x];i;i=w2[i].nextt)
    {
        int v=w2[i].to;
        if(w2[i].c&&dis[v]==dis[x]+1)
        {
            int k=dinic(v,min(flow-rest,w2[i].c));
            rest+=k;
            w2[i].c-=k;w2[i^1].c+=k;
            if(rest==flow)return rest;
        }
    }
    return rest;
}
void min_cut()
{
    int flow=0,maxflow=0;
    while(bfs())
    {
        for(int i=1;i<=n;++i)cur[i]=head2[i];
        while(flow=dinic(1,INF))maxflow+=flow;
    }
    printf("%d\n",maxflow);
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=m;++i)
    {
        int a=read(),b=read();
        int t=read(),c=read();
        add(a,b,t,c);add(b,a,t,c);
    }
    dij();
    printf("%d\n",dis[n]);
    for(int i=1;i<=tot;++i)
      if(dis[w[i].me]+w[i].t==dis[w[i].to])//说明在最短路图中 
        add2(w[i].me,w[i].to,w[i].c),add2(w[i].to,w[i].me,0);
    min_cut();
}

View Code

[AHOI2008]上学路线（最短路+最小割）

相关推荐