2015 Multi-University Training Contest 5 hdu 5352 MZL's City
39 HDU 2015 multi Contest Training University
2023-09-11 14:15:28 时间
MZL's City
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 743 Accepted Submission(s): 260
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.
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.
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.
Source
解题:拆点做最大匹配,倒着匈牙利即可以字典序最小
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 502; 4 int N,M,K; 5 struct arc { 6 int to,next; 7 arc(int x = 0,int y = -1) { 8 to = x; 9 next = y; 10 } 11 } e[2000100]; 12 int head[100010],Link[maxn],ans[maxn],tot; 13 bool used[maxn],mp[maxn][maxn]; 14 void add(int u,int v) { 15 e[tot] = arc(v,head[u]); 16 head[u] = tot++; 17 } 18 bool match(int u) { 19 for(int i = head[u]; ~i; i = e[i].next) { 20 if(!used[e[i].to]) { 21 used[e[i].to] = true; 22 if(Link[e[i].to] == -1 || match(Link[e[i].to])) { 23 Link[e[i].to] = u; 24 return true; 25 } 26 } 27 } 28 return false; 29 } 30 vector<int>con; 31 bool vis[maxn]; 32 void dfs(int u) { 33 vis[u] = true; 34 con.push_back(u); 35 for(int i = 1; i <= N; ++i) 36 if(mp[u][i] && !vis[i]) 37 dfs(i); 38 } 39 int hungary(int tot){ 40 int ret = 0; 41 memset(ans,0,sizeof ans); 42 for(int i = tot-1; i >= 0; --i){ 43 for(int j = 0; j < K; ++j){ 44 memset(used,false,sizeof used); 45 if(match(i*K + j)){ 46 ret++; 47 ans[i]++; 48 } 49 } 50 } 51 return ret; 52 } 53 int main(int c) { 54 int kase,op,u,v,tot; 55 scanf("%d",&kase); 56 while(kase--) { 57 scanf("%d%d%d",&N,&M,&K); 58 memset(head,-1,sizeof head); 59 memset(mp,false,sizeof mp); 60 memset(Link,-1,sizeof Link); 61 for(int i = tot = ::tot = 0; i < M; ++i) { 62 scanf("%d",&op); 63 switch(op) { 64 case 1: 65 memset(vis,false,sizeof vis); 66 scanf("%d",&u); 67 con.clear(); 68 dfs(u); 69 for(int j = 0; j < K; ++j) { 70 for(int k = con.size()-1; k >= 0; --k) 71 add(tot*K + j,con[k]); 72 } 73 ++tot; 74 break; 75 case 2: 76 scanf("%d%d",&u,&v); 77 mp[u][v] = mp[v][u] = true; 78 break; 79 case 3: 80 scanf("%d",&op); 81 while(op--) { 82 scanf("%d%d",&u,&v); 83 mp[u][v] = mp[v][u] = false; 84 } 85 break; 86 default: 87 break; 88 } 89 } 90 printf("%d\n",hungary(tot)); 91 for(int i = 0; i < tot; ++i) 92 printf("%d%c",ans[i],i+1==tot?'\n':' '); 93 } 94 return 0; 95 }
相关文章
- EntityFramework之DetectChanges's Secrets(三)(我为EF正名)
- What's the blur event in Html?
- What's the technical reason for "lookbehind assertion MUST be fixed length" in regex?
- What's different between INTERSECT and JOIN?
- Validation failed for one or more entities. See 'EntityValidationErrors' property for more details
- Record has Long.MIN_VALUE timestamp (= no timestamp marker). Is the time characteristic set to 'ProcessingTime', or did you forget to call 'DataStream.assignTimestampsAndWatermarks(...)
- git pull出现fatal: unable to access 'https://github.com/XXX/YYY.git'
- (转)主从同步遇到 Got fatal error 1236 from master when reading data from binary log: 'Could not find first log...
- HDU 2204 Eddy's爱好
- HDU 4738 Caocao's Bridges
- NYIST 1030 Yougth's Game[Ⅲ]
- HDU 4430 Yukari's Birthday
- Plugin 'InnoDB' registration as a STORAGE ENGINE failed
- HDU 3966 Aragorn's Story (简单树链剖分)
- HDU 4352 XHXJ's LIS (数位DP+LIS+状态压缩)
- HDU 3177 Crixalis's Equipment (贪心,差值)
- HDU 1756 Cupid's Arrow (几何问题,判定点在多边形内部)
- SAP MM MM17里不能修改物料主数据'Purchasing Value Key'字段值?
- error at ::0 can't find referenced pointcut messageInsertAspect
- Can't connect to local MySQL server through socket
- mysql异常Incorrect string value: 'xE6xB5x8BxE8xAFx95' for column 'region_name'
- MYSQL : The user specified as a definer ('root'@'%') does not exist
- 解决Setting property 'source' to 'org.eclipse.jst.jee.server的问题
- 【HDU 1009】FatMouse' Trade
- ERROR 1146 (42S02): Table 'mysql.servers' doesn't exist
- Qt error ------ 'XXX' has not been declared
- sql server该账户当前被锁定,所以用户'sa'登录失败。系统管理员无法将该账户解锁。(Microsoft SQL Server,错误:18486),登录错误18456
- ImportError: cannot import name 'Process' from 'multiprocessing'
- CommandNotFoundError: Your shell has not been properly configured to use 'conda activate'. To initialize your shell, run