网站开发那个语言好,贸易做网站,制作一个网站难吗,欧亚专线快递查询官网正题
题目链接:https://ac.nowcoder.com/acm/contest/1101#question 题目大意 nnn个点mmm条边的沙漠(所有联通子图都是仙人掌)#xff0c;删除kkk个点使得剩下的连通块最多。 解题思路
对于图上的每条割边#xff0c;删去之后就可以多出一个联通块#xff0c;所以我们就可…正题
题目链接:https://ac.nowcoder.com/acm/contest/1101#question 题目大意
nnn个点mmm条边的沙漠(所有联通子图都是仙人掌)删除kkk个点使得剩下的连通块最多。 解题思路
对于图上的每条割边删去之后就可以多出一个联通块所以我们就可以先删去所有割边。
之后图上剩下许多个环没两个环之间由一个割点连接所以我们可以用缩点双联通分量的方法找出所有的环。
我们发现对于每个环删除一条边之后就可以变成一条链也就是我们删除kkk条边就会多出k−1k-1k−1个联通块。然后我们可以对于所有的环按照大小排序然后从大的到小的分成链。 codecodecode
#includecstdio
#includecstring
#includealgorithm
#includestack
using namespace std;
const int N1e610;
struct node{int to,next;
}a[N*4];
int n,m,k,tot1,ans,c,cnt,num;
int dfn[N],low[N],ls[N],cir[N];
bool mark[N*4],flag;
stackint s;
void addl(int x,int y)
{a[tot].toy;a[tot].nextls[x];ls[x]tot;
}
void tarjan(int x,int edge)
{dfn[x]low[x]cnt;for(int ils[x];i;ia[i].next){int ya[i].to;if(!dfn[y]){tarjan(y,i);low[x]min(low[x],low[y]);if(low[y]dfn[x]){mark[i]mark[i^1]1;if(k) ans,k--;}}else if(i!(edge^1))low[x]min(low[x],dfn[y]);}
}
void tarjan2(int x)
{dfn[x]low[x]cnt;s.push(x);for(int ils[x];i;ia[i].next){if(mark[i]) continue;int ya[i].to;if(!dfn[y]){tarjan2(y);num0;low[x]min(low[x],low[y]);if(low[y]dfn[x]){int z;do{zs.top();num;s.pop();}while(z!y);num;cir[c]num;}}else low[x]min(low[x],dfn[y]);}
}
int main()
{//freopen(2.in,r,stdin);scanf(%d%d%d,n,m,k);for(int i1;im;i){int x,y;scanf(%d%d,x,y);addl(x,y);addl(y,x);}for(int i1;in;i)if(!dfn[i])tarjan(i,0),ans;cnt0;memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));for(int i1;in;i)if(!dfn[i])tarjan2(i);sort(cir1,cir1c);for(int ic;i1;i--){if(k2) break;ansmin(k,cir[i])-1;k-min(k,cir[i]);}printf(%d,ans);
}
