Pursuit For Artifacts CodeForces

https://vjudge.net/problem/CodeForces-652E

边双啊，就是点双那个tarjan里面，如果low[v]==dfn[v]（等同于low[v]>dfn[u]），表示v及其子节点只能访问到v本身，不能访问到v的祖先，那么边(u,v)是一条桥

然后再dfs一遍，不经过桥，每一次dfs得到的连通块就是一个边双。可以把一个边双缩成一个点，各个边双之间就由桥相连，得到一棵树

对于此题，可以发现，如果在一个边双内有两点a,b，还有一条边(c,d)，那么一定存在一条路径从a到c经(c,d)到d再到b（不经过重复边）（好证，不证了）upd:突然发现上面那个根本就不好证明..

证明（改编自https://codeforces.com/blog/entry/14832，那个是点双的类似结论）：

建一张新的网络流图。用(u,v,w)表示从u到v流量上限为w的边。

对原边双中每一条边(u,v)建新边(u,v,1),(v,u,1)。建新点S,T，建边(S,c,1),(S,d,1),(a,T,1),(b,T,1)

显然此时如果S到T的最大流是2，那么就存在要求的路径。

最大流=最小割，显然最小割是2

因此，只要一个边双内存在一条边有宝物，那么就存在不重复经过边的路径，从边双内给定点开始，到达边双内另一给定点，且拿到宝物

缩点成树后dfs即可

错误记录：

1.67行后多了一个反向加边；事实上由于70-74行的特殊写法，只要加一个方向的边即可

2.83行少了"|ok[u]"

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<vector>

 using namespace std;

 #define fi first

 #define se second

 #define mp make_pair

 #define pb push_back

 typedef long long ll;

 typedef unsigned long long ull;

 typedef pair<int,int> pii;

 #define N 300100

 #define M 300100

 struct E{int to,nxt;bool d;};

 namespace G

 {

 E e[M<<];

 int f1[N],ne=;

 int dfn[N],dfc;

 bool bri[M];

 void me(int a,int b,int c)

 {

     e[++ne].to=b;e[ne].nxt=f1[a];f1[a]=ne;e[ne].d=c;

     e[++ne].to=a;e[ne].nxt=f1[b];f1[b]=ne;e[ne].d=c;

 }

 int dfs(int u,int last)

 {

     int lowu=dfn[u]=++dfc,v,lowv;

     for(int k=f1[u];k;k=e[k].nxt)

     {

         v=e[k].to;

         if(!dfn[v])

         {

             lowv=dfs(v,k);

             lowu=min(lowu,lowv);

             if(lowv>dfn[u])    bri[k/]=;

         }

         else if(dfn[v]<dfn[u]&&k!=(last^))

             lowu=min(lowu,dfn[v]);

     }

     return lowu;

 }

 int now;

 int eccno[N],cnt,d[N];

 bool vis[N];

 void dfs2(int u)

 {

     eccno[u]=cnt;vis[u]=;

     for(int k=f1[u];k;k=e[k].nxt)

         if(!bri[k/])

         {

             d[cnt]|=e[k].d;

             if(!vis[e[k].to])    dfs2(e[k].to);

         }

 }

 }

 int n,m;

 namespace T

 {

 using G::eccno;using G::d;

 E e[N<<];

 int f1[N],ne=;

 void me(int a,int b,int c)

 {

     e[++ne].to=b;e[ne].nxt=f1[a];f1[a]=ne;e[ne].d=c;

 }

 void build()

 {

     int i,k;

     for(i=;i<=n;i++)

         for(k=G::f1[i];k;k=G::e[k].nxt)

             if(G::bri[k/])

                 me(eccno[i],eccno[G::e[k].to],G::e[k].d);

 }

 bool ok[N];

 void dfs(int u,int fa)

 {

     ok[u]|=d[u];

     for(int k=f1[u];k;k=e[k].nxt)

         if(e[k].to!=fa)

         {

             ok[e[k].to]|=(e[k].d|ok[u]);

             dfs(e[k].to,u);

         }

 }

 }

 int main()

 {

     int i,a,b,c;

     scanf("%d%d",&n,&m);

     for(i=;i<=m;i++)    scanf("%d%d%d",&a,&b,&c),G::me(a,b,c);

     G::dfs(,-);

     for(i=;i<=n;i++)    if(!G::vis[i])    ++G::cnt,G::dfs2(i);

     T::build();

     scanf("%d%d",&a,&b);

     T::dfs(G::eccno[a],);

     puts(T::ok[G::eccno[b]]?"YES":"NO");

     return ;

 }

巴特西

Pursuit For Artifacts CodeForces - 652E

最新文章

热门文章