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。
Solution
先Tarjan缩点，使其变为一个DAG，然后跑费用流。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 |
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> using namespace std; const int N=3000,M=30000; int n,m,Start,End,A[N],B[N],cnt,top,num,dfn[N],low[N],Stack[N],belong[N],Ans; int tot,S,T,Next[M],head[N],tree[M],val[M],Cost[M],From[M],Prev[N],dis[N],Queue[N*2]; bool visit[N],In[N]; struct node{int x,y;}Edge[M]; namespace MinCostFlow { void add(int x,int y,int z,int d) { tot++; Next[tot]=head[x]; head[x]=tot; tree[tot]=y; val[tot]=z; Cost[tot]=d; From[tot]=x; } void add_edge(int x,int y,int z,int d) { add(x,y,z,d); add(y,x,0,-d); } bool spfa() { memset(visit,0,sizeof(visit)); memset(Prev,0,sizeof(Prev)); for (int i=1;i<=T;i++) dis[i]=-1<<29; int t=0,w=1; Queue[1]=S;visit[S]=1; dis[S]=0; while (t!=w) { t++; if (t>T*2) t=1; int u=Queue[t]; if (u==T) continue; visit[u]=0; for (int i=head[u];i;i=Next[i]) if (val[i]>0) { int v=tree[i]; if (dis[v]<dis[u]+Cost[i]) { dis[v]=dis[u]+Cost[i]; Prev[v]=i; if (!visit[v]) { w++; if (w>T*2) w=1; Queue[w]=v; visit[v]=1; } } } } return Prev[T]!=0; } int GetAns() { int Flow=1<<29,ans=0; for (int i=T;Prev[i];i=From[Prev[i]]) Flow=min(val[Prev[i]],Flow); for (int i=T;Prev[i];i=From[Prev[i]]) { ans+=Cost[Prev[i]]*Flow; val[Prev[i]]-=Flow; val[Prev[i]^1]+=Flow; } return ans; } int mcf() { int ans=0; Ans=0; while (spfa()) { ans+=GetAns(); Ans++; if (ans==num) break; } return ans; } } void Tarjan(int u) { dfn[u]=low[u]=++cnt; Stack[++top]=u;In[u]=1; for (int i=head[u];i;i=Next[i]) { int v=tree[i]; if (!dfn[v]) { Tarjan(v); low[u]=min(low[v],low[u]); }else if (In[v]) low[u]=min(low[u],dfn[v]); } if (low[u]==dfn[u]) { int i; num++; do { i=Stack[top--]; belong[i]=num; In[i]=0; }while (i!=u); } } int main() { using namespace MinCostFlow; int Case; scanf("%d",&Case); while (Case--) { scanf("%d%d%d%d",&n,&m,&Start,&End); tot=1;cnt=0;top=0;num=0; memset(head,0,sizeof(head)); memset(dfn,0,sizeof(head)); memset(In,0,sizeof(In)); for (int i=1;i<=Start;i++) scanf("%d",&A[i]); for (int i=1;i<=End;i++) scanf("%d",&B[i]); for (int i=1;i<=m;i++) { scanf("%d%d",&Edge[i].x,&Edge[i].y); add(Edge[i].x,Edge[i].y,0,0); } for (int i=1;i<=n;i++) if (!dfn[i]) Tarjan(i); S=num*2+1,T=num*2+2; tot=1; memset(head,0,sizeof(head)); for (int i=1;i<=m;i++) { if (belong[Edge[i].x]!=belong[Edge[i].y]) add_edge(belong[Edge[i].x]+num,belong[Edge[i].y],1<<29,0); } for (int i=1;i<=Start;i++) add_edge(S,belong[A[i]],1<<29,0); for (int i=1;i<=End;i++) add_edge(belong[B[i]]+num,T,1<<29,0); for (int i=1;i<=num;i++) add_edge(i,i+num,1,1),add_edge(i,i+num,1<<29,0); if (mcf()==num) printf("%d\n",Ans);else puts("no solution"); } return 0; } |
