bzoj3258秘密任务

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3258

因为只走最短路，所以先正反两遍djkstra，新建边。

　　这里的边是单向边。所以要用原来的边的话不仅要把反向边打标记，还要把反向边的流量改成0！

　　但最后枚举边判flag的时候只看非反向边，如果新建边就能从2开始+=2遍历。不然无法区分是不是反向边。所以别用原来的边了吧。

求最小割得到一组可行解。流量当然就是两端点中权值较小的点的权值。

重点：

　　在残量网络上把边双连通分量缩点。剩下的边只有满流的。

　　1)非满流边：说明在S-T连通性方面等价于它的其他边的流量更小。所以它不会出现在任何可行解中。

　　2)满流边，两端点在同一个SCC中：说明两端点所在的连通块之间有非满流边，即两端点所在连通块之间的边的流量和大于两边的流量，此时应割掉两边的边；

　　　　　　　　　　所以两连通块之间的边不在任一可行解中，包括这条边。

　　3)满流边，两端点不在同一个SCC中，且不是直接连通S和T所在连通块：这说明它是在S所在块到T所在块的路径链上的一条边。

　　　　　　　　　　　　　　　　　　这条路径上每两个点之间的边的流量总和各各相等一样的感觉吧。反正路径上可以任选一个S-T割，方案就是多种的。

　　4)满流边，两端点不在同一个SCC中，且直接连通S和T所在的连通块：比如，增大它的流量，最大流的值会变大。它是必须被割的边。

jcvb（金策）的解读：

在残余网络上跑tarjan求出所有SCC，记id[u]为点u所在SCC的编号。显然有id[s]!=id[t]（否则s到t有通路，能继续增广）。

①对于任意一条满流边(u,v)，(u,v)能够出现在某个最小割集中，当且仅当id[u]!=id[v]；
②对于任意一条满流边(u,v)，(u,v)必定出现在最小割集中，当且仅当id[u]==id[s]且id[v]==id[t]。

①

<==将每个SCC缩成一个点，得到的新图就只含有满流边了。那么新图的任一s-t割都对应原图的某个最小割，从中任取一个把id[u]和id[v]割开的割即可证明。

②
<==：假设将(u,v)的边权增大，那么残余网络中会出现s->u->v->t的通路，从而能继续增广，于是最大流流量（也就是最小割容量）会增大。这即说明(u,v)是最小割集中必须出现的边。

（求SCC的正确姿势！）

（输出单词的仅首字母大写）

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#define ll long long

using namespace std;

const int N=,M=;

const ll INF=5e12;

int T,n,m,head[N],cur[N],xnt,dfn[N],low[N],tot,col[N],cnt,stack[N],top;

ll dis[][N],a[N],mxflow;

bool vis[N],bri[M<<],flag,ins[N];

struct Edge{

    int next,to;ll cap,w;

    Edge(int n=,int t=,ll c=,ll w=):next(n),to(t),cap(c),w(w) {}

}edge[M<<],ed[M<<];

int rdn()

{

    int ret=;char ch=getchar();

    while(ch>''||ch<'')ch=getchar();

    while(ch>=''&&ch<='')(ret*=)+=ch-'',ch=getchar();

    return ret;

}

int rdl()

{

    ll ret=;char ch=getchar();

    while(ch>''||ch<'')ch=getchar();

    while(ch>=''&&ch<='')(ret*=)+=ch-'',ch=getchar();

    return ret;

}

void add(int x,int y,ll w)

{

    edge[++xnt]=Edge(head[x],y,,w);head[x]=xnt;

    edge[++xnt]=Edge(head[y],x,,w);head[y]=xnt;

}

void adde(int x,int y)

{

    ll z=min(a[x],a[y]);

    ed[++xnt]=Edge(head[x],y,z,);head[x]=xnt;

    ed[++xnt]=Edge(head[y],x,,);head[y]=xnt;

}

void dj(int d)

{

    memset(dis[d],,sizeof dis[d]);dis[d][d?n:]=;

    memset(vis,,sizeof vis);

    priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > > q;

    q.push(make_pair(,d?n:));

    while(q.size())

    {

        int k=q.top().second;q.pop();

        while(vis[k]&&q.size())k=q.top().second,q.pop();

        if(vis[k])break;vis[k]=;

        for(int i=head[k],v;i;i=edge[i].next)

            if(dis[d][v=edge[i].to]>dis[d][k]+edge[i].w)

            {

                dis[d][v]=dis[d][k]+edge[i].w;q.push(make_pair(dis[d][v],v));

            }

    }

}

void init()

{

    dj();dj();int xt=xnt;xnt=;memset(head,,sizeof head);

    for(int i=;i<=xt;i++)

        if(dis[][edge[i^].to]+dis[][edge[i].to]+edge[i].w==dis[][n])adde(edge[i^].to,edge[i].to);

}

bool bfs()

{

    memset(dfn,,sizeof dfn);dfn[]=;

    queue<int> q;q.push();

    while(q.size())

    {

        int k=q.front();q.pop();

        for(int i=head[k],v;i;i=ed[i].next)

            if(!dfn[v=ed[i].to]&&ed[i].cap)

                {dfn[v]=dfn[k]+;if(v==n)return true;q.push(v);}

    }

    return false;

}

ll dinic(int k,ll flow)

{

    if(k==n)return flow;//////

    ll use=;

    for(int& i=cur[k],v;i;i=ed[i].next)

        if(dfn[v=ed[i].to]==dfn[k]+&&ed[i].cap)

        {

            ll tmp=dinic(v,min(ed[i].cap,flow-use));

            if(!tmp)dfn[v]=;

            ed[i].cap-=tmp;ed[i^].cap+=tmp;use+=tmp;

            if(use==flow)break;

        }

    return use;

}

//void dfs(int cr)

//{

//    dfn[cr]=low[cr]=++tot;

//    for(int i=head[cr],v;i;i=ed[i].next)

//        if(ed[i].cap)

//        {

//            if(dfn[v])low[cr]=min(low[cr],dfn[v]);

//            else{dfs(v);low[cr]=min(low[cr],low[v]);}

//            if(low[v]>dfn[cr])bri[i]=1;

//        }

//}

//void dfs2(int cr)

//{

//    col[cr]=cnt;

//    for(int i=head[cr];i;i=ed[i].next)

//        if(ed[i].cap&&!bri[i]&&!col[ed[i].to])dfs2(ed[i].to);

//}

//void tarjan()

//{

//    memset(col,0,sizeof col);memset(bri,0,sizeof bri);memset(dfn,0,sizeof dfn);

//    cnt=0;tot=0;dfs(1);

//    for(int i=1;i<=n;i++)if(!col[i])cnt++,dfs2(i);

//}

void dfs(int cr)

{

    dfn[cr]=low[cr]=++tot;stack[++top]=cr;ins[cr]=;

    for(int i=head[cr],v;i;i=ed[i].next)

        if(ed[i].cap)

        {

            if(ins[v=ed[i].to])low[cr]=min(low[cr],dfn[v]);

            else if(!dfn[v])//所以自己必须赋值为0

                {dfs(v);low[cr]=min(low[cr],low[v]);}

        }

    if(dfn[cr]==low[cr])

    {

        cnt++;while(stack[top]!=cr)ins[stack[top]]=,col[stack[top--]]=cnt;

        ins[stack[top]]=;col[stack[top--]]=cnt;

    }

}

void tarjan()

{

    memset(dfn,,sizeof dfn);cnt=;tot=;

    for(int i=;i<=n;i++)if(!dfn[i])dfs(i);

}

int main()

{

    T=rdn();

    while(T--)

    {

        xnt=;memset(head,,sizeof head);

        n=rdn();m=rdn();

        for(int i=;i<n;i++)a[i]=rdl();a[n]=INF;int x,y;ll z;

        for(int i=;i<=m;i++)

        {

            x=rdn();y=rdn();z=rdl();add(x,y,z);

        }

        init();mxflow=;

        while(bfs())

            {memcpy(cur,head,sizeof head);mxflow+=dinic(,INF);}

        tarjan();flag=;

        for(int i=,u,v;i<=xnt;i+=)//只看非反向边

            if(!ed[i].cap&&col[u=ed[i^].to]!=col[v=ed[i].to])//

                if(a[u]==a[v]||col[u]!=col[]||col[v]!=col[n]){flag=;break;}

        if(flag)printf("No %lld\n",mxflow);else printf("Yes %lld\n",mxflow);

    }

    return ;

}

巴特西

bzoj3258秘密任务

最新文章

热门文章