【Foreign】最大割 [线性基]

最大割

Time Limit: 15 Sec Memory Limit: 256 MB

Description

Input

Output

Sample Input

　　3 6
　　1 2 1
　　1 2 1
　　3 3 111
　　1 3 101101
　　1 2 1011
　　2 3 111011

Sample Output

　　1
　　0
　　0
　　101101
　　101101
　　110000

HINT

　　l = log2(w)

Solution

　　首先我们发现，由于XOR满足消去律，那么我们定义一个新点的点权为该点所有连边的XOR和，那么任意点XOR起来得到的值正是割的值，所以这样操作之后问题就转化为了：任取几个点，求XOR出的最大值，支持点权修改。

　　那么我们现在显然得到了做法：线性基，并且我们需要维护一个可修改的线性基。

　　线性基的加入方法：1.从大到小加入，如果这一位没有匹配元则加入当前值当作匹配元，退出；2.如果这一位有匹配元了就XOR完向后继续执行操作，若值=0则退出。

　　线性基的最值方法：用一个初值为0的Ans串，从大到小贪心，如果这一位有匹配元并且Ans串该位为0则XOR，继续向后。

　　线性基的维护方法：我们另外记录一个record表示这个基是由哪些值XOR出来的，比如我们要消去b，然后我们就用一个 有bXOR出来且主元最小 的基来消去其它含b的基中的b，其中主元定义为最高位的1，我们让最高位的1最小，这样往上消去的时候依然可以满足XOR出来可以满足线性基的条件性质。然后我们扫一遍，如果含有这个b则XOR一下，并且record要XOR那个基的record，这样才可以保证record的记录不漏。

　　这道题就是先删除，然后再加入，每次询问求最值即可。

Code

 #include<iostream>

 #include<algorithm>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<bitset>

 using namespace std;

 const int ONE = ;

 const int L = ;

 int T,n,x,y;

 int PD;

 char s[ONE];

 int Link[ONE];

 bitset <L> record[ONE],A[ONE];

 bitset <L> Ans,P;

 int get()

 {

         int res,Q=;    char c;

         while( (c=getchar())< || c>)

         if(c=='-')Q=-;

         if(Q) res=c-;

         while((c=getchar())>= && c<=)

         res=res*+c-;

         return res*Q;

 }

 void Deal_first()

 {

         scanf("%s",s+);

         int len = strlen(s+);

         P.reset();

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

             P[L-len+i] = s[i]-'';

 }

 void Add(int k)

 {

         for(int pos=;pos<=L;pos++)

         if(A[k][pos])

         {

             if(!Link[pos])

             {

                 Link[pos] = k;

                 break;

             }

             else

             {

                 A[k] ^= A[Link[pos]];

                 record[k] ^= record[Link[pos]];

                 if(!A[k].any()) break;

             }

         }

 }

 void Update(int x)

 {

         int k=;

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

         if(record[i][x] && !A[i].any())

         {

             k=i;

             break;

         }

         if(!k)

         {

             for(int i=L;i>=;i--)

             {

                 if(Link[i] && record[Link[i]][x])

                 {

                     k = Link[i];

                     Link[i] = ;

                     break;

                 }

             }

         }

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

         {

             if(i!=k && record[i][x])

             {

                 A[i] ^= A[k];

                 record[i] ^= record[k];

             }

         }

         A[k] ^= P; Add(k);

 }

 int main()

 {

         n=get();    T=get();

         for(int i=;i<=n;i++) record[i][i] = ;

         while(T--)

         {

             x=get();    y=get();

             Deal_first();

             Update(x);    Update(y);

             Ans.reset(); PD=;

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

             {

                 if(Link[i] && !Ans[i]) Ans ^= A[Link[i]];

                 if(Ans[i]) PD=;

                 if(PD) printf("%d",Ans[i]?:);

             }

             if(!PD) printf("");

             printf("\n");

         }

 }

巴特西