Zq's Blog DFS,图论,算法 [DFS]CF883G:Orientation of Edges

[DFS]CF883G:Orientation of Edges

题目大意

给定一个$N$个点$M$条边且没有自环的图,图中既有有向边和无向边的图,从$S$出发,将所有的无向边改成有向边,求能够遍历到的最大最小点数,以及各自的任一方案。

题解

从$S$开始刷一趟DFS,碰到有向边就DFS下去,无向边$(u,v)$则分两种,求最大时$u\to v$,求最小时$v\to u$(其中$u$是当前遍历到的点);易得这样是最优的;

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int N,M,S,Ans,TP[300005];
bool vis[300005],col[300005];
int tot,son[600005],nxt[600005],lnk[300005],Id[600005],tp[600005],Xs[600005];
inline void add(int x,int y,int id,int type,int A){son[++tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;Id[tot]=id;tp[tot]=type;Xs[tot]=A;}
void DFS(int x,int l){
    Ans++;
    for (int i=lnk[x];i;i=nxt[i]){
        if (son[i]==l||vis[son[i]]) continue;
        if (tp[i]==2) col[Id[i]]=Xs[i];
        vis[son[i]]=1;DFS(son[i],x);
    }
}
void DFS_(int x,int l){
    Ans++;
    for (int i=lnk[x];i;i=nxt[i]){
        if (son[i]==l||vis[son[i]]) continue;
        if (tp[i]==2) col[Id[i]]=Xs[i]^1;
        else vis[son[i]]=1,DFS_(son[i],x);
    }
}
inline int read(){
    int Res=0;char ch=getchar();
    while (ch>'9'||ch<'0') ch=getchar();
    while (ch>='0'&&ch<='9') Res=Res*10+ch-'0',ch=getchar();
    return Res;
}
int main()
{
    N=read();M=read();S=read();
    for (int i=1;i<=M;i++){
        int t=read(),x=read(),y=read();
        add(x,y,i,t,1);
        if (t==2) add(y,x,i,t,0);
        TP[i]=t;
    }
    vis[S]=1;DFS(S,0);
    printf("%d\n",Ans);
    for (int i=1;i<=M;i++){
        if (TP[i]!=2) continue;
        if (col[i]) printf("+");else printf("-");
    }
    printf("\n");
    memset(vis,0,sizeof vis);Ans=0;
    memset(col,0,sizeof col);
    vis[S]=1;DFS_(S,0);
    printf("%d\n",Ans);
    for (int i=1;i<=M;i++){
        if (TP[i]!=2) continue;
        if (col[i]) printf("+");else printf("-");
    }
    return 0;
}

1 thought on “[DFS]CF883G:Orientation of Edges”

发表评论

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