主要思路:网络流。
思路
先考虑最小生成树,如果一条边边权大于等于选中的边,那么这条边是否删去没有任何影响。
按边权排序,对于边 \((u,v,L)\),若要加上当且仅当 \(u\) 和 \(v\) 并不联通。
把所有边权比选定的边的边权小的边拿出来连上,流量均为 \(1\),最小割。
最大树同理,连上边权比选定的边的边权大的边,接着跑最大流。
两次答案相加。
AC code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf = 1e9 + 7;
struct node {
int nxt, to, val;
} e[3000005];
int num = 1, h[250000], s, t;
void add(int from, int to, int dis) {
e[++num].nxt = h[from],e[num].to = to,e[num].val = dis,h[from] = num,e[++num].nxt = h[to],e[num].to = from,e[num].val = 1,h[to] = num;
}
queue<int>q;
int n, m, ans, dep[250000];
int u[2500000], v[2500000], w[2500000], l;
bool bfs(int s,int t){
memset(dep,0x3f,sizeof(dep));
while(!q.empty())q.pop();
dep[s]=0;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].to;
if(dep[v]>inf&&e[i].val){
dep[v]=dep[u]+1;
q.push(e[i].to);
}
}
}
if(dep[t]<inf)return 1;
return 0;
}
int dfs(int u,int t,int lim){
if(!lim||t==u)return lim;
int flow=0,f;
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].to;
int &w=e[i].val;
if(dep[v]==dep[u]+1&&(f=dfs(v,t,min(lim,w)))){
flow+=f;
lim-=f;
w-=f;
e[i^1].val+=f;
if(!lim)break;
}
}
return flow;
}
void dinic(int s, int t) {
while (bfs(s, t))ans += dfs(s, t, inf);
}
signed main() {
cin >> n >> m;
for (int i = 1; i <= m; i++)cin >> u[i] >> v[i] >> w[i];
cin >> s >> t >> l;
for (int i = 1; i <= m; i++)if (w[i] < l)add(v[i], u[i], 1);
dinic(s, t);
memset(h,0,sizeof(h));
num=1;
for(int i=1;i<=m;i++)if(w[i]>l)add(v[i],u[i],1);
dinic(s,t);
cout<<ans;
return 0;
}
标签:nxt,P5934,val,int,题解,边权,dep,num,2012
From: https://www.cnblogs.com/aub-unluck-beginning/p/18382078