[BZOJ3931][CQOI2015]网络吞吐量 最短路+最大流



一遍最短路拿出所有能用的边,然后拆点最大流.
谁知道为什么这么慢,竟然BZ倒第四...

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 2333
#define M 502333
#define in(i) (i)
#define out(i) ((i)+n)
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3fabcdefll;
int s,t,n,m,head[N],to[M],nxt[M],d[M],can[M],tot=1;
ll f[M];
inline void add(int x,int y,int z,ll w)
{
    to[++tot]=y;d[tot]=z;f[tot]=w;nxt[tot]=head[x];head[x]=tot;
    to[++tot]=x;d[tot]=z;f[tot]=0;nxt[tot]=head[y];head[y]=tot;
}
ll dis[2][N];
struct Node{ll d;int x;};
bool operator <(Node a,Node b){return a.d>b.d;}
priority_queue<Node>q;
void dij(bool flag)
{
    while(!q.empty())q.pop();
    for(int i=0;i<=t;i++)dis[flag][i]=INF;
    if(flag)dis[1][t]=0,q.push((Node){0,t});
    else dis[0][s]=0,q.push((Node){0,s});
    Node k;int i,y;
    while(!q.empty())
    {
        k=q.top();q.pop();
        for(i=head[k.x];i;i=nxt[i])
        {
            y=to[i];
            if(dis[flag][y]>k.d+d[i])
            {
                dis[flag][y]=k.d+d[i];
                q.push((Node){dis[flag][y],y});
            }
        }
    }
}
int deep[N],Q[N],l=1,r;
bool bfs()
{
    memset(deep,-1,sizeof deep);
    l=1,r=0;
    Q[++r]=s;deep[s]=0;
    int x,i,y;
    while(l<=r)
    {
        x=Q[l++];
        for(i=head[x];i;i=nxt[i])
        {
            y=to[i];
            if(deep[y]==-1&&f[i]&&can[i])
            {
                deep[y]=deep[x]+1;
                if(y==t)return 1;
                Q[++r]=y;
            }
        }
    }
    return 0;
}
ll dinic(int x,ll flow)
{
    if(x==t)return flow;
    int a;ll temp=flow;
    for(int i=head[x];i;i=nxt[i])if(deep[to[i]]==deep[x]+1&&f[i]&&can[i])
    {
        a=dinic(to[i],min(temp,f[i]));
        if(!a)deep[to[i]]=-1;
        temp-=a,f[i]-=a,f[i^1]+=a;
        if(!temp)return flow;
    }
    return flow-temp;
}
ll maxflow()
{
    ll re=0;
    while(bfs())re+=dinic(s,inf);
    return re;
}
int main()
{
    cin>>n>>m;
    s=1,t=n*2;
    for(int x,y,z,i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        add(out(x),in(y),z,INF);
        add(out(y),in(x),z,INF);
    }
    for(int c,i=1;i<=n;i++)
    {
        scanf("%d",&c);
        add(in(i),out(i),0,c);
        if(i==1||i==n)add(in(i),out(i),0,INF),add(out(i),in(i),0,INF);
    }
    dij(0);dij(1);
    for(int i,x=1;x<=t;++x)
    {
        for(i=head[x];i;i=nxt[i])
            if(dis[0][x]+d[i]+dis[1][to[i]]==dis[0][t]||dis[1][x]+d[i]+dis[0][to[i]]==dis[1][s])
                can[i]=1;
    }
    cout<<maxflow();
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注