题解 AT696 【グラフ】

· · 题解

说一种虽然不是正解但确实是对的的方法吧。

方法来自于ET2006神仙跟我偶然扯到的神仙算法。

翻译：给定一张有向图，我们在图上找出两条路径P_1=\{V_1,E_1\},P_2=\{V_2,E_2\}，路径可以有重复的点或边。求\max(|V_1\cup V_2|)。

思路：

路径问题，首选SCC（强连通分量）缩点，因为同一块强连通分量里的所有点肯定是互相可达的。

缩完点后，我们得到一张DAG。

现在问题转换为：给你一张带权DAG，找出两条路径，使得它们并集的权值最大。

正解是DP（毕竟这是DP Contest嘛）

不过我们可以发现，这个模型有点像费用流！我们拆个点限制每个点的权值只会被计入一次，然后建立一个伪源点和伪汇点s,t限制流量最多只能为2。

具体的说，我们将每个点x拆成入点x和出点x'两个点。定义(u,v,w,c)表示一条从u到v，流量上限为w，费用为c的边。

对于缩点后的图上每一条边(u,v)，连边(u',v,2,0)；

对于缩点后的图上每个点u，连边(s,u,2,0)、(u,u',1,val_u)、(u,u',1,0)和(u',t,2,0)。注意到我们在u和u'间连了两条边，这样费用只会被计入一次。

最后，连边(S,s,2,0)和(t,T,2,0)，以限制流量。

答案即为最大费用最大流。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,col[310],c,sz[310],s,t;
namespace SCC{
    int tot,dfn[310],low[310],head[310],cnt;
    struct node{
        int to,next;
    }edge[200100];
    void ae(int u,int v){
    //  cout<<u<<" "<<v<<endl;
        edge[cnt].next=head[u],edge[cnt].to=v,head[u]=cnt++;
    }
    stack<int>stk;
    void Tarjan(int x){
        dfn[x]=low[x]=++tot,stk.push(x);
        for(int i=head[x];i!=-1;i=edge[i].next){
            if(!dfn[edge[i].to])Tarjan(edge[i].to),low[x]=min(low[x],low[edge[i].to]);
            if(!col[edge[i].to])low[x]=min(low[x],dfn[edge[i].to]);
        }
        if(low[x]<dfn[x])return;
        c++;
        while(stk.top()!=x)col[stk.top()]=c,stk.pop(),sz[c]++;
        col[stk.top()]=c,stk.pop(),sz[c]++;
    }
}
namespace MCMF{
    const int N=1000,M=200000;
    int head[N],cnt,dis[N],fr[N],id[N],S,T,cost;
    struct node{
        int to,next,val,cost;
    }edge[M];
    void ae(int u,int v,int w,int c){
//      printf("%d %d %d %d\n",u,v,w,c);
        edge[cnt].cost=c,edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].val=w,head[u]=cnt++;
        edge[cnt].cost=-c,edge[cnt].next=head[v],edge[cnt].to=u,edge[cnt].val=0,head[v]=cnt++;
    }
    queue<int>q;
    bool in[N];
    bool SPFA(){
        memset(dis,0x80,sizeof(dis)),dis[S]=0,q.push(S),in[S]=true;
        while(!q.empty()){
            int x=q.front();q.pop(),in[x]=false;
    //      printf("%d\n",x);
            for(int i=head[x];i!=-1;i=edge[i].next){
                if(!edge[i].val)continue;
                if(dis[edge[i].to]<dis[x]+edge[i].cost){
                    dis[edge[i].to]=dis[x]+edge[i].cost,fr[edge[i].to]=x,id[edge[i].to]=i;
                    if(!in[edge[i].to])in[edge[i].to]=true,q.push(edge[i].to);
                }
            }
        }
        if(dis[T]==dis[0])return false;
        int x=T,mn=0x3f3f3f3f;
        while(x!=S)mn=min(mn,edge[id[x]].val),x=fr[x];
        cost+=dis[T]*mn,x=T;
        while(x!=S)edge[id[x]].val-=mn,edge[id[x]^1].val+=mn,x=fr[x];
        return true;
    }
}
int main(){
    scanf("%d",&n),memset(SCC::head,-1,sizeof(SCC::head)),memset(MCMF::head,-1,sizeof(MCMF::head));
    for(int i=1;i<=n;i++)for(int j=1,x;j<=n;j++){
        scanf("%d",&x);
        if(x)SCC::ae(i,j);
    }
    for(int i=1;i<=n;i++)if(!SCC::dfn[i])SCC::Tarjan(i);
//  for(int i=1;i<=n;i++)printf("%d\n",col[i]);
    MCMF::S=c*2+1,MCMF::T=c*2+2,s=c*2+3,t=c*2+4;
    for(int i=1;i<=n;i++)for(int j=SCC::head[i];j!=-1;j=SCC::edge[j].next){
        if(col[SCC::edge[j].to]==col[i])continue;
        MCMF::ae(col[i]+c,col[SCC::edge[j].to],2,0);
    }
    for(int i=1;i<=c;i++)MCMF::ae(s,i,2,0);
    for(int i=1;i<=c;i++)MCMF::ae(i+c,t,2,0);
    MCMF::ae(MCMF::S,s,2,0),MCMF::ae(t,MCMF::T,2,0);
    for(int i=1;i<=c;i++)MCMF::ae(i,i+c,1,sz[i]),MCMF::ae(i,i+c,1,0);
    while(MCMF::SPFA());
    printf("%d\n",MCMF::cost);
    return 0;
}