[***]HZOJ 哪一天她能重回我身边

%%%神仙题。

居然是图论，我还一直以为是二分图或者啥数据结构。

直接说正解了，将数看作节点，牌看做边，从牌的正面的数想反面连边权为1的边，反面向正面连边权为0的边（注意用到成对存储的技巧，之后会非常巧妙地用到），可以发现就是要求反转几条边可以使每个点的出读小于等于1。那么每个联通图只可能是树或基环树。可以先dfs判断求出每个联通图的点数np和边数ne，若ne/2(双向边)>np，那么这个联通图不合法直接输出-1 -1即可。

 void dfs(int x,int fa)

 {

     vi[x]=;np++;

     for(int i=f(x);i;i=n(i))

     {

             ne++;

         if(v(i)!=fa)

             if(!vi[v(i)])dfs(v(i),x);

     }

 }

 bool pd()

 {

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

     if(!vi[i])

     {

         np=ne=,dfs(i,);

         if(np<ne/)return ;

     }

     return ;

 }

代码实现

接下来考虑他是树的情况：

对于确定的跟节点，翻转的边的个数就是将所有点指向父亲节点（可以动手画一下），可以用树形dp求得。但是要枚举根节点吗？其实可以用到二次扫描和换根法，设以x为根要反转的边数为f[x],那么其实f[son]可以用f[x]更新：如果x->son的边权为1，则f[son]=f[x]-1,否则f[son]=f[x]+1.这样我们就解决了树的情况。

 int f[MAXN],st,en,ned;

 void dfs1(int x,int fa)

 {

     v[x]=;f[x]=;

     for(int i=f(x);i;i=n(i))

     if(v(i)!=fa)

     {

         if(!v[v(i)])

         {

             dfs1(v(i),x);

             f[x]+=f[v(i)]+w(i);

         }

         else st=u(i),en=v(i),ned=i;

     }

 }

 int f2[MAXN];

 vector<int> tem;

 void dfs2(int x,int fa)

 {

     tem.push_back(f2[x]);

     for(int i=f(x);i;i=n(i))

     if(v(i)!=fa && i!=ned && i!=(ned^))

     {

         if(w(i))f2[v(i)]=f2[x]-;

         else    f2[v(i)]=f2[x]+;

         dfs2(v(i),x);

     }

 }

代码实现

下面看基环树：

在dfs时找出环上的随机一条边记录，将它去掉按树处理，最后在考虑这条边的影响。那么边的成对储存就有用了，将边的编号%2就是它从u指向v的权值。

                 ned%=;

                 if(f2[st]+ned==f2[en]+(ned^))minn=;

                 else minn=;

                 ans+=min(f2[st]+ned,f2[en]+(ned^));

代码实现

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<vector>

 #define MAXN 200010

 #define mod 998244353

 #define LL long long

 #define int LL

 #define ma(x) memset(x,0,sizeof(x))

 using namespace std;

 struct edge

 {

     int u,v,w,nxt;

     #define u(x) ed[x].u

     #define v(x) ed[x].v

     #define w(x) ed[x].w

     #define n(x) ed[x].nxt

 }ed[MAXN*];

 int first[MAXN],num_e=;

 #define f(x) first[x]

 int T,n;

 int np,ne;

 bool v[MAXN],vi[MAXN];

 void dfs(int x,int fa)

 {

     vi[x]=;np++;

     for(int i=f(x);i;i=n(i))

     {

             ne++;

         if(v(i)!=fa)

             if(!vi[v(i)])dfs(v(i),x);

     }

 }

 bool pd()

 {

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

     if(!vi[i])

     {

         np=ne=,dfs(i,);

         if(np<ne/)return ;

     }

     return ;

 }

 int f[MAXN],st,en,ned;

 void dfs1(int x,int fa)

 {

     v[x]=;f[x]=;

     for(int i=f(x);i;i=n(i))

     if(v(i)!=fa)

     {

         if(!v[v(i)])

         {

             dfs1(v(i),x);

             f[x]+=f[v(i)]+w(i);

         }

         else st=u(i),en=v(i),ned=i;

     }

 }

 int f2[MAXN];

 vector<int> tem;

 void dfs2(int x,int fa)

 {

 //    v[x]=1;

     tem.push_back(f2[x]);

     for(int i=f(x);i;i=n(i))

     if(v(i)!=fa && i!=ned && i!=(ned^))

     {

         if(w(i))f2[v(i)]=f2[x]-;

         else    f2[v(i)]=f2[x]+;

 //        if(!v[v(i)])

         dfs2(v(i),x);

     }

 }

 inline void add(int u,int v,int w);

 signed main()

 {

 //    freopen("back5.in","r",stdin);

 //    freopen("1.out","w",stdout);

     cin>>T;

     while(T--)

     {

         ma(f);ma(f2);ma(v);ma(vi);ma(first);num_e=;tem.clear();

         scanf("%lld",&n);

         int a,b;

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

         {

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

             add(a,b,);add(b,a,);

         }

         if(pd()){puts("-1 -1");continue;}

         int minn=,ans=,ans2=;

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

         if(!v[i])

         {

             st=en=ned=-;tem.clear();minn=;

             dfs1(i,);

             f2[i]=f[i];

             dfs2(i,);

             if(st==-)

             {

                 sort(tem.begin(),tem.end());

                 for(int j=;j<tem.size();j++)

                 if(tem[j]==tem[])minn++;

                 else break;

                 ans+=tem[];

             }

             else

             {

                 ned%=;

                 if(f2[st]+ned==f2[en]+(ned^))minn=;

                 else minn=;

                 ans+=min(f2[st]+ned,f2[en]+(ned^));

             }

             ans2=(ans2*minn)%mod;

         }

         printf("%lld %lld\n",ans,ans2);

     }

 }

 inline void add(int u,int v,int w)

 {

     ++num_e;

     u(num_e)=u;

     v(num_e)=v;

     w(num_e)=w;

     n(num_e)=f(u);

     f(u)=num_e;

 }

完整代码

巴特西

[***]HZOJ 哪一天她能重回我身边

最新文章

热门文章