广州网站开发方案,网站系统平台建设,网站开发的基本条件,门户平台是什么意思正题
题目链接:https://www.luogu.com.cn/problem/P5934 题目大意
给出nnn个点mmm条边的一张图#xff0c;再加入一条边(u,v,L)(u,v,L)(u,v,L)求至少删掉多少条边可以使得这条边即在最小生成树上又在最大生成树上。 1≤n≤2104,1≤m≤21051\leq n\leq 2\times 10^4,1\leq m\…正题
题目链接:https://www.luogu.com.cn/problem/P5934 题目大意
给出nnn个点mmm条边的一张图再加入一条边(u,v,L)(u,v,L)(u,v,L)求至少删掉多少条边可以使得这条边即在最小生成树上又在最大生成树上。
1≤n≤2×104,1≤m≤2×1051\leq n\leq 2\times 10^4,1\leq m\leq 2\times 10^51≤n≤2×104,1≤m≤2×105 解题思路
稍微思考一下就不难发现这两个问其实是没有影响的因为第一个问显然只需要删去边权小于LLL的第二个问显然只需要删去边权大于LLL的。所以考虑分开求然后相加
那么考虑怎么让它在最小生成树上。考虑我们之前LCT\text{LCT}LCT维护最小生成树的做法我们加入一条边(u,v,w)(u,v,w)(u,v,w)的时候是找到u∼vu\sim vu∼v路径上的最大边然后和www比较。
那么如果原图中存在一条不经过这条边的路径且最大值比u,vu,vu,v要小。那么显然这条路径可以完全取代这条边所以这条边一定不是最小生成树上的边。
那么同理我们只需要把所有边权小于LLL的边加入然后再删去最少的边使得u,vu,vu,v不连通即可。这个用最小割解决就好了。
最大生成树同理 code
#includecstdio
#includecstring
#includealgorithm
#includequeue
using namespace std;
const int N2e410,M2e510,inf1e9;
struct node{int to,next,w;
}a[M1];
struct edge{int x,y,w;
}e[M];
int n,m,s,t,L,tot1,ls[N],dep[N],ans;
queueint q;
void addl(int x,int y,int w){a[tot].toy;a[tot].nextls[x];ls[x]tot;a[tot].ww;a[tot].tox;a[tot].nextls[y];ls[y]tot;a[tot].ww;return;
}
bool bfs(){while(!q.empty())q.pop();q.push(s);memset(dep,0,sizeof(dep));dep[s]1;while(!q.empty()){int xq.front();q.pop();for(int ils[x];i;ia[i].next){int ya[i].to;if(dep[y]||!a[i].w)continue;dep[y]dep[x]1;if(yt)return 1;q.push(y);}}return 0;
}
int dinic(int x,int flow){if(xt)return flow;int rest0,k;for(int ils[x];i;ia[i].next){int ya[i].to;if(dep[x]1!dep[y]||!a[i].w)continue;rest(kdinic(y,min(flow-rest,a[i].w)));a[i].w-k;a[i^1].wk;if(restflow)return flow;}if(!rest)dep[x]0;return rest;
}
int main()
{scanf(%d%d,n,m);for(int i1;im;i)scanf(%d%d%d,e[i].x,e[i].y,e[i].w);scanf(%d%d%d,s,t,L);for(int i1;im;i)if(e[i].wL)addl(e[i].x,e[i].y,1);while(bfs())ansdinic(s,inf);memset(ls,0,sizeof(ls));tot0;for(int i1;im;i)if(e[i].wL)addl(e[i].x,e[i].y,1);while(bfs())ansdinic(s,inf);printf(%d\n,ans);return 0;
}
