最大割
Time Limit: 15 Sec Memory Limit: 256 MBDescription
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
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 10 const int ONE = 2001; 11 const int L = 1005; 12 13 int T,n,x,y; 14 int PD; 15 char s[ONE]; 16 int Link[ONE]; 17 18 bitset record[ONE],A[ONE]; 19 bitset Ans,P; 20 21 int get() 22 { 23 int res,Q=1; char c; 24 while( (c=getchar())<48 || c>57) 25 if(c=='-')Q=-1; 26 if(Q) res=c-48; 27 while((c=getchar())>=48 && c<=57) 28 res=res*10+c-48; 29 return res*Q; 30 } 31 32 void Deal_first() 33 { 34 scanf("%s",s+1); 35 int len = strlen(s+1); 36 P.reset(); 37 for(int i=1;i<=len;i++) 38 P[L-len+i] = s[i]-'0'; 39 } 40 41 void Add(int k) 42 { 43 for(int pos=1;pos<=L;pos++) 44 if(A[k][pos]) 45 { 46 if(!Link[pos]) 47 { 48 Link[pos] = k; 49 break; 50 } 51 else 52 { 53 A[k] ^= A[Link[pos]]; 54 record[k] ^= record[Link[pos]]; 55 if(!A[k].any()) break; 56 } 57 } 58 } 59 60 void Update(int x) 61 { 62 int k=0; 63 for(int i=1;i<=n;i++) 64 if(record[i][x] && !A[i].any()) 65 { 66 k=i; 67 break; 68 } 69 70 if(!k) 71 { 72 for(int i=L;i>=1;i--) 73 { 74 if(Link[i] && record[Link[i]][x]) 75 { 76 k = Link[i]; 77 Link[i] = 0; 78 break; 79 } 80 } 81 } 82 83 for(int i=1;i<=n;i++) 84 { 85 if(i!=k && record[i][x]) 86 { 87 A[i] ^= A[k]; 88 record[i] ^= record[k]; 89 } 90 } 91 92 A[k] ^= P; Add(k); 93 } 94 95 int main() 96 { 97 n=get(); T=get(); 98 for(int i=1;i<=n;i++) record[i][i] = 1; 99 while(T--)100 {101 x=get(); y=get();102 Deal_first();103 Update(x); Update(y);104 105 Ans.reset(); PD=0;106 for(int i=1;i<=L;i++)107 {108 if(Link[i] && !Ans[i]) Ans ^= A[Link[i]];109 if(Ans[i]) PD=1;110 if(PD) printf("%d",Ans[i]?1:0);111 }112 if(!PD) printf("0");113 printf("\n");114 }115 }