首先肯定每一位單獨考慮，對于每一位，源點連向該位點權為0的節(jié)點inf的邊，點權為1的節(jié)點連向匯點inf的邊，每一條無向邊拆成兩條流量為1的有向邊，跑最小割。

考慮一組割，一定將原圖劃分成源點和匯點兩部分，那么左半部分都選0，右半部分都選1，那么它的代價就是割的代價，即要求最小割。

為了讓點的值最小，相當于要讓匯點集合的點數(shù)盡量少，那么直接從匯點搜一遍，將所有能走到的節(jié)點記為1，其他記為0即可。

還有一種做法比較神奇，將兩點之間的邊權增加為10000（需要大于總點數(shù)即可），然后再讓源點向每一個點再連一條1的邊，最小割一定是在10000最少的前提下（即圖的點權最小）讓源點割掉的點最少（源點割掉的每一條邊都是到匯點集合的點）。

1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 505 4 #define inf 0x3f3f3f3f 5 struct ji{ 6 int nex,to,len; 7 }e[N*20],edge[N*20]; 8 queue<int>q; 9 int E,EE,n,m,x,y,a[N],w[N],head[N],work[N],d[N]; 10 long long ans1,ans2; 11 void add(int x,int y,int z){ 12 edge[E].nex=head[x]; 13 edge[E].to=y; 14 edge[E].len=z; 15 head[x]=E++; 16 if (E&1)add(y,x,0); 17 } 18 bool bfs(){ 19 memset(d,-1,sizeof(d)); 20 q.push(0); 21 d[0]=0; 22 while (!q.empty()){ 23 int k=q.front(); 24 q.pop(); 25 for(int i=head[k];i!=-1;i=edge[i].nex) 26 if ((edge[i].len)&&(d[edge[i].to]<0)){ 27 d[edge[i].to]=d[k]+1; 28 q.push(edge[i].to); 29 } 30 } 31 return d[n+1]>=0; 32 } 33 int dfs(int k,int s){ 34 if (k>n)return s; 35 int p; 36 for(int &i=work[k];i!=-1;i=edge[i].nex) 37 if ((edge[i].len)&&(d[edge[i].to]==d[k]+1)){ 38 p=dfs(edge[i].to,min(s,edge[i].len)); 39 if (p){ 40 edge[i].len-=p; 41 edge[i^1].len+=p; 42 return p; 43 } 44 } 45 return 0; 46 } 47 int dinic(){ 48 int k,ans=0; 49 while (bfs()){ 50 memcpy(work,head,sizeof(head)); 51 while (k=dfs(0,inf))ans+=k; 52 } 53 return ans; 54 } 55 int main(){ 56 scanf("%d%d",&n,&m); 57 memset(head,-1,sizeof(head)); 58 for(int i=1;i<=n;i++)scanf("%d",&w[i]); 59 for(int i=1;i<=m;i++){ 60 scanf("%d%d",&x,&y); 61 add(x,y,10000); 62 add(y,x,10000); 63 } 64 for(int i=1;i<=n;i++) 65 if (w[i]<0)add(0,i,1); 66 else ans2+=w[i]; 67 EE=E; 68 memcpy(a,head,sizeof(a)); 69 memcpy(e,edge,sizeof(e)); 70 for(int i=0;i<31;i++){ 71 E=EE; 72 memcpy(head,a,sizeof(a)); 73 memcpy(edge,e,sizeof(e)); 74 for(int j=1;j<=n;j++) 75 if (w[j]>=0) 76 if (w[j]&(1<<i))add(j,n+1,inf); 77 else add(0,j,inf); 78 int p=dinic(); 79 ans1+=p/10000*(1LL<<i); 80 ans2+=p%10000*(1LL<<i); 81 } 82 printf("%lld\n%lld",ans1,ans2); 83 } View Code

?

轉載于:https://www.cnblogs.com/PYWBKTDA/p/11249672.html

總結

以上是生活随笔為你收集整理的[bzoj2400]Optimal Marks的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。