MZL's City(ネットワークストリーム)
9524 ワード
MZL's City
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 496 Accepted Submission(s): 164
Problem Description
MZL is an active girl who has her own country.
Her big country has N cities numbered from 1 to N.She has controled the country for so long and she only remebered that there was a big earthquake M years ago,which made all the roads between the cities destroyed and all the city became broken.She also remebered that exactly one of the following things happened every recent M years:
1.She rebuild some cities that are connected with X directly and indirectly.Notice that if a city was rebuilt that it will never be broken again.
2.There is a bidirectional road between city X and city Y built.
3.There is a earthquake happened and some roads were destroyed.
She forgot the exactly cities that were rebuilt,but she only knew that no more than K cities were rebuilt in one year.Now she only want to know the maximal number of cities that could be rebuilt.At the same time she want you to tell her the smallest lexicographically plan under the best answer.Notice that 8 2 1 is smaller than 10 0 1.
Input
The first contains one integer T(T<=50),indicating the number of tests.
For each test,the first line contains three integers N,M,K(N<=200,M<=500,K<=200),indicating the number of MZL’s country ,the years happened a big earthquake and the limit of the rebuild.Next M lines,each line contains a operation,and the format is “1 x” , “2 x y”,or a operation of type 3.
If it’s type 3,first it is a interger p,indicating the number of the destoyed roads,next 2*p numbers,describing the p destoyed roads as (x,y).It’s guaranteed in any time there is no more than 1 road between every two cities and the road destoyed must exist in that time.
Output
The First line Ans is the maximal number of the city rebuilt,the second line is a array of length of tot describing the plan you give(tot is the number of the operation of type 1).
Sample Input
Sample Output
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 496 Accepted Submission(s): 164
Problem Description
MZL is an active girl who has her own country.
Her big country has N cities numbered from 1 to N.She has controled the country for so long and she only remebered that there was a big earthquake M years ago,which made all the roads between the cities destroyed and all the city became broken.She also remebered that exactly one of the following things happened every recent M years:
1.She rebuild some cities that are connected with X directly and indirectly.Notice that if a city was rebuilt that it will never be broken again.
2.There is a bidirectional road between city X and city Y built.
3.There is a earthquake happened and some roads were destroyed.
She forgot the exactly cities that were rebuilt,but she only knew that no more than K cities were rebuilt in one year.Now she only want to know the maximal number of cities that could be rebuilt.At the same time she want you to tell her the smallest lexicographically plan under the best answer.Notice that 8 2 1 is smaller than 10 0 1.
Input
The first contains one integer T(T<=50),indicating the number of tests.
For each test,the first line contains three integers N,M,K(N<=200,M<=500,K<=200),indicating the number of MZL’s country ,the years happened a big earthquake and the limit of the rebuild.Next M lines,each line contains a operation,and the format is “1 x” , “2 x y”,or a operation of type 3.
If it’s type 3,first it is a interger p,indicating the number of the destoyed roads,next 2*p numbers,describing the p destoyed roads as (x,y).It’s guaranteed in any time there is no more than 1 road between every two cities and the road destoyed must exist in that time.
Output
The First line Ans is the maximal number of the city rebuilt,the second line is a array of length of tot describing the plan you give(tot is the number of the operation of type 1).
Sample Input
1
5 6 2
2 1 2
2 1 3
1 1
1 2
3 1 1 2
1 2
Sample Output
3
0 2 1
Hint
No city was rebuilt in the third year,city 1 and city 3 were rebuilt in the fourth year,and city 2 was rebuilt in the sixth year. : n , M , , . m , , : 1.> 1,x, x . 2.> 2,x,y x y 3.> 3,p, p , 2p , p ; . ; : ; , , ; s k , t 1 ; , 1 ; , ; AC :
/* ***********************************************
Author :xdlove
Created Time :2015 07 31 12 37 29
File Name :a.cpp
************************************************ */
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
/**
* **/
#define FOR(i,s,t) for(int i = (s); i < (t); i++)
#define FOR_REV(i,s,t) for(int i = (s - 1); i >= (t); i--)
#define mid ((l + r) >> 1)
#define clr(a) memset(a,0,sizeof(a))
#define lson l,mid,u<<1
#define rson mid+1,r,u<<1|1
#define ls u<<1
#define rs u<<1|1
typedef long long ll;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const double pi = acos(-1.0);
/**
* **/
class Fast
{
public:
inline void rd(int &ret)
{
char c;
int sgn;
if(c = getchar(),c == EOF) return;
while(c != '-' && (c < '0' || c > '9')) c = getchar();
sgn = (c == '-') ? -1 : 1;
ret = (c == '-') ? 0 : (c - '0');
while(c = getchar(),c >= '0' && c <= '9')
ret = ret * 10 + c - '0';
ret *= sgn;
}
public:
inline void pt(int x)
{
if(x < 0)
{
putchar('-');
x = -x;
}
if(x > 9) pt(x / 10);
putchar(x % 10 + '0');
}
};
Fast xd;
const int MAXM = 1e6;
const int MAXN = 1000;
struct Node
{
int from,to,next;
int cap;
}edge[MAXM * 2];
int tol;
int Head[MAXN];
int que[MAXN];
int dep[MAXN]; //dep
int stack[MAXN];//stack ，
int cur[MAXN],cnt;//
void Init()
{
tol = cnt = 0;
memset(Head,-1,sizeof(Head));
}
void add_edge(int u, int v, int w)
{
//printf("%d: %d: %d
",u,v,w);
edge[tol].from = u;
edge[tol].to = v;
edge[tol].cap = w;
edge[tol].next = Head[u];
Head[u] = tol++;
edge[tol].from = v;
edge[tol].to = u;
edge[tol].cap = 0;
edge[tol].next = Head[v];
Head[v] = tol++;
}
int BFS(int start, int end)
{
int front, rear;
front = rear = 0;
memset(dep, -1, sizeof(dep));
que[rear++] = start;
dep[start] = 0;
while (front != rear)
{
int u = que[front++];
if (front == MAXN)front = 0;
for (int i = Head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].to;
if (edge[i].cap > 0 && dep[v] == -1)
{
dep[v] = dep[u] + 1;
que[rear++] = v;
if (rear >= MAXN)rear = 0;
if (v == end)return 1;
}
}
}
return 0;
}
int dinic(int start, int end)
{
int res = 0;
int top;
while (BFS(start, end))
{
memcpy(cur, Head, sizeof(Head));
int u = start;
top = 0;
while (true)
{
if (u == end)
{
int min = INF;
int loc;
for (int i = 0; i < top; i++)
if (min > edge[stack[i]].cap)
{
min = edge[stack[i]].cap;
loc = i;
}
for (int i = 0; i < top; i++)
{
edge[stack[i]].cap -= min;
edge[stack[i] ^ 1].cap += min;
}
res += min;
top = loc;
u = edge[stack[top]].from;
}
for (int i = cur[u]; i != -1; cur[u] = i = edge[i].next)
if (edge[i].cap != 0 && dep[u] + 1 == dep[edge[i].to])
break;
if (cur[u] != -1)
{
stack[top++] = cur[u];
u = edge[cur[u]].to;
}
else
{
if (top == 0)break;
dep[u] = -1;
u = edge[stack[--top]].from;
}
}
}
return res;
}
int g[205][205],used[205];
int Stack[600];
int n,m,k;
void dfs(int u)
{
used[u] = 1;
add_edge(cnt,u + m,1);
FOR(v, 1, 1 + n)
{
if(g[u][v] && !used[v])
{
used[v] = 1;
dfs(v);
}
}
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int T;
xd.rd(T);
while(T--)
{
Init();
xd.rd(n);
xd.rd(m);
xd.rd(k);
clr(g);
clr(used);
vector<int> p;
FOR(i, 0, m)
{
int o,x,y;
xd.rd(o);
if(o == 2)
{
xd.rd(x);
xd.rd(y);
g[x][y] = g[y][x] = 1;
}
else if(o == 3)
{
xd.rd(o);
FOR(i, 0, o)
{
xd.rd(x);
xd.rd(y);
g[x][y] = g[y][x] = 0;
}
}
else
{
cnt++;
clr(used);
p.push_back(cnt);
xd.rd(x);
dfs(x);
}
}
int s = 0,t = n + m + 1;
for(int i = 1; i <= n; i++)
add_edge(i + m,t,1);
int pos = 0,sum = 0;
for(vector<int> :: iterator it = --p.end(); ; it--)
{
int id = *it;
//cout<<id<<endl;
add_edge(s,id,k);
Stack[pos++] = dinic(s,t);
sum += Stack[pos - 1];
if(it == p.begin()) break;
}
printf("%d
",sum);
FOR_REV(i,pos,0)
{
if(i != pos - 1) putchar(' ');
printf("%d",Stack[i]);
}
puts("");
}
return 0;
}