第一问先求1到n的最短路。第二问求破坏一些路使得1到n的最短路变大。每条路被破坏都要花费一定的代价Ci。求min∑Ci。

我学会了写spfa好开心啊！我学会了写dinic好开心啊！==

破坏边使不连通明显最小割水掉嘛、、

好了言归正传、先求出所有的最短路。然后判断每条边是不是在1~n的最短路上。是的话就连边。然后再新建的图上做最小割。

一开始建图建错了、、应该这么建：首先以1为源点跑spfa，记录d[0][i]为1~i的最短路。然后以n为源点跑spfa，记录d[1][i]为n~i的最短路。

如果i在1~n的最短路上那一定满足d[0][i]+d[1][i]==d[0][n]（这也是第一问的答案、、）且d[0][i]+w(i,j)=d[0][j]。

然后就没了、、继续fread然后刷到rank5、、、

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxm=250000,maxn=505,inf=2000000009;
struct edge{int t,c,next;}E[maxm];
char buf[3000000],*pt=buf;
int p[maxm],w[maxm],c[maxm],n1[maxm],h[maxn],v[maxn],d[2][maxn],q[maxm],V[maxn],level[maxn],n,m,tot=0,tt=0,S,T,An=inf;
inline int getint(){
    int r=0; while(*pt<'0'||*pt>'9')pt++; while(*pt>='0'&&*pt<='9')r=r*10+*pt++-48;return r;
}inline void ae1(int u,int v,int t,int cc){
    p[tot]=v;   w[tot]=t;   c[tot]=cc;  n1[tot]=h[u];   h[u]=tot++;
    p[tot]=u;   w[tot]=t;   c[tot]=cc;  n1[tot]=h[v];   h[v]=tot++;
}inline void ae2(int a,int b,int c){
    E[tt].t=b; E[tt].c=c; E[tt].next=V[a];   V[a]=tt++;
    E[tt].t=a; E[tt].c=0; E[tt].next=V[b];   V[b]=tt++;
}inline int bfs(){
    memset(level,0xff,sizeof(level));   int head=0,tail=1;  q[0]=S; level[S]=1;
    while(head<tail){
        int u=q[head++];    if(u==T)return 1;
        for(int p=V[u];p!=-1;p=E[p].next)
            if(E[p].c>0 && level[E[p].t]==-1) level[E[p].t]=level[u]+1,q[tail++]=E[p].t;
    }return 0;
}int dfs(int u=S,int lmt=inf){
    if(u==T)    return lmt; int ret=0,  delta;
    for(int p=V[u];p!=-1;p=E[p].next){
        if(E[p].c>0 && level[E[p].t]==level[u]+1){
            delta=dfs(E[p].t,min(lmt-ret,E[p].c));
            E[p].c-=delta;  E[p^1].c+=delta;    ret+=delta;
            if(ret==lmt)    return ret;
        }
    }if(!ret)   level[u]=-1;    return ret;
}inline int dinic(){
    int ret=0;S=1,T=n;
    for(int i=1;i<=n;i++)for(int j=h[i];~j;j=n1[j])
        if(d[0][p[j]]+d[1][p[j]]==An && d[0][i]+w[j]==d[0][p[j]]) ae2(i,p[j],c[j]);
    while(bfs())ret+=dfs(); return ret;
}inline void spfa(int SS,int f){
    for(int i=1;i<=n;i++)d[f][i]=inf; memset(v,0,sizeof(v));
    int head=0,tail=1;  q[0]=SS; v[SS]=1; d[f][SS]=0;
    while(head<tail){
        int u=q[head++];    v[u]=0;
        for(int i=h[u];~i;i=n1[i])
            if(d[f][u]+w[i]<d[f][p[i]]){
                d[f][p[i]]=d[f][u]+w[i];  if(!v[p[i]])  v[p[i]]=1,  q[tail++]=p[i];
            }
    }
}int main(){
    fread(pt,1,3000000,stdin);  n=getint(),m=getint();  memset(h,-1,sizeof(h)); memset(V,-1,sizeof(V));
    for(int u,v,t,c,i=1;i<=m;u=getint(),v=getint(),t=getint(),c=getint(),ae1(u,v,t,c),i++);
    spfa(1,0);  spfa(n,1);  for(int i=1;i<=n;i++)   An=min(An,d[0][i]+d[1][i]);
    printf("%d\n%d\n",An,dinic()); return 0;
}

• 相关文章