网站备案ip查询网站,软件外包公司名单,wordpress媒体库远程上传,wordpress注册代码正题
题目链接:https://www.ybtoj.com.cn/contest/117/problem/2 题目大意 nnn个人#xff0c;每人有aia_iai个属于自己的物品。mmm次交换依次进行#xff0c;每次xi,yix_i,y_ixi,yi两个人可以决定拿不拿自己的一个物品进行交换。
求111号人最后能拿到最多多少种物品…正题
题目链接:https://www.ybtoj.com.cn/contest/117/problem/2 题目大意
nnn个人每人有aia_iai个属于自己的物品。mmm次交换依次进行每次xi,yix_i,y_ixi,yi两个人可以决定拿不拿自己的一个物品进行交换。
求111号人最后能拿到最多多少种物品
1≤n,m,ai≤30001\leq n,m,a_i\leq 30001≤n,m,ai≤3000 解题思路
每种物品只需要一个所以每种物品的第一个可以视为流量aia_iai可以视为自己的物品处的空位自己的物品可以不视为自己的。
xi,yix_i,y_ixi,yi的交换可以视为一条流量为111的双向边因为依次进行所以要分成mmm层然后每一层有交换的连边。
发现这样有很多点没有用到去掉这些多余的那点数就是O(nm)O(nm)O(nm)级别的了
跑最大流就好了 code
#includecstdio
#includecstring
#includealgorithm
#includequeue
using namespace std;
const int N12100,inf1e9;
struct node{int to,next,w;
}a[N2];
int T,n,m,tot,cnt,ans,s,t;
int ls[N],dep[N],p[N],w[N];
queueint q;
void addl(int x,int y,int w){a[tot].toy;a[tot].nextls[x];ls[x]tot;a[tot].ww;a[tot].tox;a[tot].nextls[y];ls[y]tot;a[tot].w0;return;
}
bool bfs(){memset(dep,0,sizeof(dep));dep[s]1;while(!q.empty())q.pop();q.push(s);while(!q.empty()){int xq.front();q.pop();for(int ils[x];i;ia[i].next){int ya[i].to;if(dep[y]||!a[i].w)continue;dep[y]dep[x]1;if(yt)return 1;q.push(y);} }return 0;
}
int dinic(int x,int flow){if(xt)return flow;int rest0,k;for(int ils[x];i;ia[i].next){int ya[i].to;if(dep[x]1!dep[y]||!a[i].w)continue;rest(kdinic(y,min(a[i].w,flow-rest)));a[i].w-k;a[i^1].wk;if(restflow)return rest;}if(!rest)dep[x]0;return rest;
}
int main()
{freopen(collection.in,r,stdin);freopen(collection.out,w,stdout);scanf(%d,T);while(T--){tot0;memset(ls,0,sizeof(ls));scanf(%d%d,n,m);stot1;tcnt2;ans0;for(int i1;in;i){p[i]cnt;scanf(%d,w[i]);addl(s,p[i],1);}for(int i1;im;i){int x,y;scanf(%d%d,x,y);cnt;addl(p[x],cnt,w[x]);p[x]cnt;cnt;addl(p[y],cnt,w[y]);p[y]cnt;addl(p[x],p[y],1);addl(p[y],p[x],1);}addl(p[1],t,inf);while(bfs())ansdinic(s,inf);printf(%d\n,ans);}return 0;
}
