首页 > 代码库 > BZOJ2893: 征服王
BZOJ2893: 征服王
题解:
裸的上下界最小流是有问题的。
因为在添加了附加源之后求出来的流，因为s，t以及其它点地位都是平等的。
如果有一个流经过了s和t，那么总可以认为这个流是从s出发到t的满足题意的流。
既然可能存在s到t的流，那么也可能会存在不经过s和t的流，而这是一条环流！！起点不是s，也不是t！显然不满足题意！！！
为了避免环流的出现，我们只好缩点。。。（本来想偷懒不缩的。。。）
所以整个算法就是缩点之后上下界最小流。
代码：无压力rank1了。。。
1 #include<cstdio> 2 3 #include<cstdlib> 4 5 #include<cmath> 6 7 #include<cstring> 8 9 #include<algorithm> 10 11 #include<iostream> 12 13 #include<vector> 14 15 #include<map> 16 17 #include<set> 18 19 #include<queue> 20 21 #include<string> 22 23 #define inf 1000000000 24 25 #define maxn 100000+5 26 27 #define maxm 100000+5 28 29 #define eps 1e-10 30 31 #define ll long long 32 33 #define pa pair<int,int> 34 35 #define for0(i,n) for(int i=0;i<=(n);i++) 36 37 #define for1(i,n) for(int i=1;i<=(n);i++) 38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 42 43 #define for4(i,x) for(int i=head[x],y;i;i=e[i].next) 44 45 #define mod 1000000007 46 47 using namespace std; 48 49 inline int read() 50 51 { 52 53 int x=0,f=1;char ch=getchar(); 54 55 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 56 57 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 58 59 return x*f; 60 61 } 62 int n,m,s,t,ss,tt,T,a[maxn],b[maxn],maxflow,tot=1,head[maxn],cur[maxn],h[maxn],in[maxn]; 63 queue<int>q; 64 struct edge{int go,next,v;}e[maxm]; 65 inline void add(int x,int y,int v) 66 { 67 e[++tot]=(edge){y,head[x],v};head[x]=tot; 68 e[++tot]=(edge){x,head[y],0};head[y]=tot; 69 } 70 inline void ins(int x,int y) 71 { 72 e[++tot]=(edge){y,head[x],0};head[x]=tot; 73 } 74 inline void insert(int x,int y,int l,int r) 75 { 76 in[y]+=l;in[x]-=l;add(x,y,r-l); 77 } 78 void build() 79 { 80 for0(i,tt)if(in[i]>0)add(ss,i,in[i]);else if(in[i]<0)add(i,tt,-in[i]); 81 } 82 bool bfs() 83 { 84 for(int i=0;i<=tt;i++)h[i]=-1; 85 q.push(s);h[s]=0; 86 while(!q.empty()) 87 { 88 int x=q.front();q.pop(); 89 for(int i=head[x];i;i=e[i].next) 90 if(e[i].v&&h[e[i].go]==-1) 91 { 92 h[e[i].go]=h[x]+1;q.push(e[i].go); 93 } 94 } 95 return h[t]!=-1; 96 } 97 int dfs(int x,int f) 98 { 99 if(x==t) return f;100 int tmp,used=0;101 for(int i=cur[x];i;i=e[i].next)102 if(e[i].v&&h[e[i].go]==h[x]+1)103 {104 tmp=dfs(e[i].go,min(e[i].v,f-used));105 e[i].v-=tmp;if(e[i].v)cur[x]=i;106 e[i^1].v+=tmp;used+=tmp;107 if(used==f)return f; 108 }109 if(!used) h[x]=-1;110 return used;111 }112 void dinic()113 {114 maxflow=0;115 while(bfs())116 {117 for (int i=0;i<=tt;i++)cur[i]=head[i];maxflow+=dfs(s,inf);118 }119 }120 int ti,u[maxn],v[maxn],low[maxn],dfn[maxn],cnt,scc[maxn],top,sta[maxn];121 int minflow()122 {123 s=ss;t=tt;124 dinic();125 if(maxflow!=cnt)return -1;126 int ans=e[tot].v;127 e[tot].v=e[tot^1].v=0;128 s=cnt+cnt+1;t=0;129 dinic();130 return ans-maxflow;131 }132 inline void tarjan(int x)133 {134 sta[++top]=x;low[x]=dfn[x]=++ti;135 for4(i,x)if(!dfn[y=e[i].go])136 {137 tarjan(y);138 low[x]=min(low[x],low[y]);139 }else if(!scc[y])low[x]=min(low[x],dfn[y]);140 if(low[x]==dfn[x])141 {142 cnt++;143 for(int y=0;y!=x;)scc[y=sta[top--]]=cnt;144 }145 }146 147 int main()148 149 {150 151 freopen("input.txt","r",stdin);152 153 freopen("output.txt","w",stdout);154 155 T=read();156 while(T--)157 {158 memset(head,0,sizeof(head));tot=1;cnt=0;159 memset(in,0,sizeof(in));160 memset(low,0,sizeof(low));161 memset(dfn,0,sizeof(dfn));162 memset(scc,0,sizeof(scc));163 n=read();m=read();a[0]=read();b[0]=read();164 for1(i,a[0])a[i]=read();165 for1(i,b[0])b[i]=read();166 for1(i,m){u[i]=read();v[i]=read();ins(u[i],v[i]);}167 for1(i,n)if(!dfn[i])tarjan(i);168 s=0;t=cnt+cnt+1;ss=t+1;tt=t+2;169 memset(head,0,sizeof(head));tot=1;170 for1(i,cnt)insert(i,i+cnt,1,inf);171 for1(i,a[0])insert(s,scc[a[i]],0,inf);172 for1(i,b[0])insert(scc[b[i]]+cnt,t,0,inf);173 for1(i,m)if(scc[u[i]]!=scc[v[i]])insert(scc[u[i]]+cnt,scc[v[i]],0,inf);174 build();175 insert(t,s,0,inf);176 int x=minflow();177 if(x==-1)printf("no solution\n");else printf("%d\n",x);178 }179 180 return 0;181 182 }
2893: 征服王
Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 64 Solved: 17
[Submit][Status]
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。
BZOJ2893: 征服王
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。