bzoj2893 征服王

bzoj2893 征服王

​​ Description 虽然春希将信息传递给了雪菜，但是雪菜却好像完全不认得春希了。心急如焚的春希打开了第二世代机能，对雪菜的脑内芯片进行了直连-hack。 进入到雪菜内部的春希发现（这什么玩意。。），雪菜的脑部结构被分成了n个块落，并且一些块落之间被有向边连接着。由于四分五裂的脑部，雪菜关于春希的记忆也完全消失，春希为了恋人，启动了inversionprocess. 在inversion process中，要想使雪菜回到正常状态，需要纳米机器人的帮助。纳米机器人可以从任意一个可以作为起点的块落出发进行修复，也可以在任意一个可以作为终点的块落结束修复（并不是到了某个终点就一定要停止）。春希希望所有的节点都能被修复(只要纳米机器人到过该点就算修复过)，这样才能让雪菜重获新生。 作为纳米机器人1号的你能帮助春希算算至少需要多少个机器人才能拯救雪菜吗？ 当然，如果无论如何都无法使得春希的愿望被满足的话，请输出”no solution”（不包括引号） Input 题目包含多组数据 第1行有一个正整数t，表示数据的组数。 第2行有两个正整数n、m，a，b，分别表示块落的数量、有向边的数量、起点的数量、终点的数量。 第3行有a个正整数，表示可以作为起点的块落。 第4行有b个正整数，表示可以作为终点的块落。 第5行至第m+4行，每行有两个正整数u、v，表示能从编号为u的块落到编号为v的块落。 之后以此类推。 Output 输出共有t行，每行输出对应数据的答案。 Sample Input

2 2 1 1 1 1 2 2 1 3 2 3 3 1 2 3 1 2 3 1 2 1 3 Sample Output

no solution 2 【数据规模和约定】 对于30%的数据，满足n <= 10, m <= 100。 对于60%的数据，满足n <= 200, m <= 5000。 对于100%的数据，满足t<=10,n <= 1000, m <= 10000。 题面乍一看 哎哟和leoly的noi接站问题一样啊 但是仔细一看 不仅多组数据 而且n<=1000心凉凉啊 n^3gg 怎么办 还是icefox和leoly强啊 orz 首先先tarjan缩点 然后每个点拆开限制流量为1 然后跑带下界的最小流即可 为什么一定要缩点呢 看了下网上的问题 看一下这张图 他的最小流是0 因为可以看作这环内一直有3 的流量在转圈走 上下界的网络流有的点要多流出有的点要多流入最小流是在这个基础上去求的算法可以判断是否流量平衡 但是不能保证是否真的是从源点流出来的

#include#include#include#include#include#define N 2200#define M 11000#define inf 0x3f3f3f3fusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0;char ch=gc(); while(ch<'0'||ch>'9') ch=gc(); while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();} return x;}struct node{ int x,y,z,next;}data[M<<2],data1[M];int level[N],scc,b[N],n,m,a,bb,h[N],h1[N],start[N],end[N],num=1,S,T,s,t,cur[N],dfn[N],low[N],stackf[N];inline void insert1(int x,int y,int z){ data[++num].y=y;data[num].z=z;data[num].next=h[x];h[x]=num;data[num].x=x; data[++num].y=x;data[num].z=0;data[num].next=h[y];h[y]=num;data[num].x=y;}inline void insert2(int x,int y){ data1[++num].y=y;data1[num].next=h1[x];h1[x]=num;data1[num].x=x;}inline bool bfs(){ queueq;memset(level,0,sizeof(level));level[S]=1;q.push(S); while(!q.empty()){ int x=q.front();q.pop(); for (int i=h[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z; if (level[y]||!z) continue;level[y]=level[x]+1;if (y==T) return 1;q.push(y); } }return 0;}inline int dfs(int x,int s){ if (x==T) return s;int ss=s,tt=h[x]; for (int i=cur[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z; if (level[x]+1==level[y]&&z){ int xx=dfs(y,min(z,s));if (!xx) level[y]=0;tt=i; s-=xx;data[i].z-=xx;data[i^1].z+=xx;if (!s){cur[x]=i;return ss;} } }cur[x]=tt;return ss-s;}stackqq;inline void tarjan(int x){ dfn[x]=low[x]=++num;stackf[x]=1;qq.push(x); for (int i=h1[x];i;i=data1[i].next){ int y=data1[i].y; if (!dfn[y]) tarjan(y),low[x]=min(low[x],low[y]);else if (stackf[y]) low[x]=min(low[x],dfn[y]); } if (dfn[x]==low[x]){ ++scc;int y; do{ y=qq-();stackf[y]=0;b[y]=scc;qq.pop(); }while(y!=x); }}int x[M],y[M],TT;int main(){ //freopen("bzoj2893.in","r",stdin); TT=read(); while(TT--){ n=read();m=read();a=read();bb=read();num=0;memset(h,0,sizeof(h)); memset(h1,0,sizeof(h1));scc=0;int ans=0;memset(dfn,0,sizeof(dfn)); for (int i=1;i<=a;++i) start[i]=read(); for (int i=1;i<=bb;++i) end[i]=read(); for (int i=1;i<=m;++i){x[i]=read(),y[i]=read();insert2(x[i],y[i]);} num=0;for (int i=1;i<=n;++i) if (!dfn[i]) tarjan(i);num=1;s=0;t=scc*2+1;S=t+1;T=S+1; for (int i=1;i<=m;++i){if (b[x[i]]==b[y[i]]) continue;insert1(scc+b[x[i]],b[y[i]],inf);} for (int i=1;i<=scc;++i) insert1(S,i+scc,1),insert1(i,T,1),insert1(i,i+scc,inf); for (int i=1;i<=a;++i) insert1(s,b[start[i]],inf);for (int i=1;i<=bb;++i) insert1(scc+b[end[i]],t,inf); while(bfs()) memcpy(cur,h,sizeof(h)),ans+=dfs(S,inf);insert1(t,s,inf); while(bfs()) memcpy(cur,h,sizeof(h)),ans+=dfs(S,inf); if (ans!=scc) printf("no solution\n");else printf("%d\n",data[num].z); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。