bzoj5421:收藏家

bzoj5421

贴一张图

关于对问题的转化：

当两个人交换收藏品时，显然我们进行这个操作是为了得到更优解。

那么一个收藏品是有用的，另一个被换走的收藏品可以当做直接扔掉了。

所以只要保留一个就可以了。

注意边数、点数要开够

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<queue>

 using namespace std;

 #define N 20010

 int min(int a,int b){return a<b?a:b;}

 int n,m,u,S,T,val[N],d[N],cur[N],fir[N]; bool vis[N];

 int cnt,hd[N],nxt[N<<],ed[N],poi[N<<];

 int cap[N<<],flow[N<<],ans;

 queue <int> h;

 void adde(int x,int y,int v1,int v2){

     nxt[ed[x]]=++cnt; hd[x]=hd[x]?hd[x]:cnt;

     ed[x]=cnt; poi[cnt]=y; flow[cnt]=v1; cap[cnt]=v2;

 }

 #define to poi[i]

 bool bfs(){

     memset(vis,,sizeof(vis));

     h.push(S); vis[S]=; d[S]=;

     while(!h.empty()){

         int x=h.front(); h.pop();

         for(int i=hd[x];i;i=nxt[i])

             if(!vis[to]&&cap[i]>flow[i]){

                 vis[to]=; d[to]=d[x]+;

                 h.push(to);

             }

     }return vis[T];

 }

 int dinic(int x,int a){

     if(!a||x==T) return a;

     int F=,f;

     for(int &i=cur[x];i&&a;i=nxt[i])

         if(d[to]==d[x]+&&(f=dinic(to,min(a,cap[i]-flow[i])))>){

             F+=f; flow[i]+=f;

             a-=f; flow[i^]-=f;

         }

     return F;

 }

 void nect(int x,int y,int v){adde(x,y,,v);adde(y,x,,);}//一条边以及它的反向边

 int main(){

     int TuT;scanf("%d",&TuT);

     while(TuT--){

         memset(hd,,sizeof(hd));

         memset(nxt,,sizeof(nxt));

         memset(ed,,sizeof(ed));cnt=;

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

         S=;T=u=;ans=;

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

             scanf("%d",&val[i]);

             nect(S,++u,);fir[i]=u;

         }

         for(int i=,q1,q2;i<=m;++i){

             scanf("%d%d",&q1,&q2);

             nect(fir[q1],++u,val[q1]);fir[q1]=u;

             nect(fir[q2],++u,val[q2]);fir[q2]=u;

             nect(fir[q1],fir[q2],);

             nect(fir[q2],fir[q1],);

         }nect(fir[],T,val[]);

         while(bfs()){//普通dinic

             for(int i=;i<=u;++i) cur[i]=hd[i];

             ans+=dinic(S,2e9);

         }printf("%d\n",ans);

     }return ;

 }