|
MZL's City
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 546 Accepted Submission(s): 185
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.
Source 2015 Multi-University Training Contest 5 题意：有n个城市，m年（可认为是m个操作），每年最多可修复 k 个城市。 操作 : 1 x ：表示在当年可以修复与 x 直接或间接相连的城市（每个城市只能修复1次，且每年最多可修复 k 个城市） 2 x y ：表示在当年修了一条路
无向的。 3 p 接下来p条路 x y ：表示当年毁坏p条路
最后答案输出两行：第一行输出最多能 修复多少个城市。 第二行输出1操作对应的每年修复的城市个数（输出的序列字典序最小）。
解题：最小费用最大流。首先用二维数组记录路的连接状况。建图：把年数也看作一个点year+n 并与超极源点vs建边，边容为k，费用为m（m为递减的,这样加一个费用是为了找出字典序最小的解（先流向年限最大的））则该边为< vs , year+n , k , m> 。如果遇到操作1 ，那么就用bfs或dfs找出与x相连的点Y，再新增一些边< year+n , Y , 1 , 0 > ，最后再连接每个 i 城市与超极汇点 vt 的边 < i , vt , 1 , 0 > ，边容为1是因为每个城市只能修复 1 次。最后跑一次最小费用最大流 ，最大流就是最多能修复的城市，源点流向每一年的流最就是每年可修复的城市数量。
#include
#include
#include
using namespace std; const int MAXN = 1010; const int MAXM = 100100; const int INF = 1<<30; struct EDG{ int to,next,cap,flow; int cost; //单价 }edg[MAXM]; int head[MAXN],eid; int pre[MAXN], cost[MAXN] ; //点0~(n-1) void init(){ eid=0; memset(head,-1,sizeof(head)); } void addEdg(int u,int v,int cap,int cst){ edg[eid].to=v; edg[eid].next=head[u]; edg[eid].cost = cst; edg[eid].cap=cap; edg[eid].flow=0; head[u]=eid++; edg[eid].to=u; edg[eid].next=head[v]; edg[eid].cost = -cst; edg[eid].cap=0; edg[eid].flow=0; head[v]=eid++; } bool inq[MAXN]; int q[MAXN]; bool spfa(int sNode,int eNode,int n){ int l=0 , r=0; for(int i=0; i
0 && cost[v]>cost[u]+edg[i].cost){ //在满足可增流的情况下，最小花费 cost[v] = cost[u]+edg[i].cost; pre[v]=i; //记录路径上的边 if(!inq[v]){ if(r==MAXN)r=0; q[r++]=v; inq[v]=1; } } } } return cost[eNode]!=INF; //判断有没有增广路 } //反回的是最大流，最小花费为minCost int minCost_maxFlow(int sNode,int eNode ,int& minCost,int n){ int ans=0; while(spfa(sNode,eNode,n)){ int mint=INF; for(int i=pre[eNode]; i!=-1; i=pre[edg[i^1].to]){ if(mint>edg[i].cap-edg[i].flow) mint=edg[i].cap-edg[i].flow; } ans+=mint; for(int i=pre[eNode]; i!=-1; i=pre[edg[i^1].to]){ edg[i].flow+=mint; edg[i^1].flow-=mint; minCost+=mint*edg[i].cost; } } return ans; } int vist[MAXN],mapt[MAXN][MAXN],year; void bfs(int u , int n)//找出与u相连的点 { queue
q; memset(vist,0,sizeof(vist)); vist[u]=1; q.push(u); while(!q.empty()) { u=q.front(); q.pop(); for(int i=1; i<=n; i++) if(!vist[i]&&mapt[u][i]) vist[i]=1,q.push(i); } for(int i=1; i<=n; i++) if(vist[i]) addEdg(year+n , i , 1 , 0); } int main() { int n,m,k ,op , u ,v; int T; scanf(%d,&T); while(T--) { scanf(%d%d%d,&n,&m,&k); memset(mapt,0,sizeof(mapt)); init(); year=0; int vs=0 ,vt = n+m+1; for(int i=1; i<=n; i++) addEdg(i , vt , 1 , 0); while(m--){ scanf(%d%d,&op,&u); if(op==3) { int p=u ; while(p--){ scanf(%d%d,&u,&v); mapt[u][v]=mapt[v][u]=0; } } else{ if(op==2){ scanf(%d,&v); mapt[u][v]= mapt[v][u]=1; } else{ year++; addEdg(vs , year+n , k , m); bfs(u , n); } } } int ans,tans[505] ; ans=minCost_maxFlow(vs , vt , m , vt+1); for(int i=head[vs]; i!=-1; i=edg[i].next ) tans[edg[i].to-n]=edg[i].flow; printf(%d ,ans); for(int i=1; i<=year; i++) if(i
|