【bzoj 2521】 [Shoi2010] 最小生成树（网络流最小割）

本文主要是介绍【bzoj 2521】 [Shoi2010] 最小生成树（网络流最小割），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

2521: [Shoi2010]最小生成树

Time Limit: 10 Sec   Memory Limit: 128 MB
Submit: 429   Solved: 250
[ Submit][ Status][ Discuss]

Description

Input

Output

Sample Input

Sample Output

HINT

Source

[ Submit][ Status][ Discuss]

【题解】【网络流最小割】

【由最小生成树（kruskal）可知，若一条边必出现在一个图的最小生成树中，当且仅当用小于当前边的边不可使这条边控制的两个点相连】

【由这一性质可得网络流建图方法：将原图中所有不大于指定边的权值的边的权值改为val[id]-val[j]+1建入图中，双向连边（由于不确定行走方向），然后以指定边连接的两个点作为源点和汇点跑最小割，并输出答案即可】

<strong>#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct map{int s,t,v;
}d[810];
int a[4010],nxt[4010],p[510],val[4010],tot;
int cur[510],dis[510],last[510],num[510];
int n,m,id,ans;
bool b[510];
inline void add(int x,int y,int v)
{tot++; a[tot]=y; nxt[tot]=p[x]; p[x]=tot; val[tot]=v;tot++; a[tot]=x; nxt[tot]=p[y]; p[y]=tot; val[tot]=0;
}
inline int  addflow(int s,int t)
{int s1=0x7fffffff,now=t;while(now!=s) {s1=min(s1,val[last[now]]);now=a[last[now]^1];}now=t;while(now!=s){val[last[now]^1]+=s1;val[last[now]]-=s1;now=a[last[now]^1];}return s1;
}
inline void bfs(int l)
{queue<int>que;for(int i=1;i<=n;++i) dis[i]=n;memset(b,0,sizeof(b));que.push(l); dis[l]=0; b[l]=true;while(!que.empty()){int u,v;u=que.front(); que.pop();v=p[u];while(v!=-1){if(!b[a[v]]&&val[v^1]){b[a[v]]=1;que.push(a[v]);dis[a[v]]=dis[u]+1;}v=nxt[v];}}return;
}
inline int isap(int s,int t)
{int sum=0,now=s,i;bfs(t);for(i=1;i<=n;++i) num[dis[i]]++;for(i=1;i<=n;++i) cur[i]=p[i];while(dis[s]<n){if(now==t){sum+=addflow(s,t);now=s;}bool h=false;int u=cur[now];while(u!=-1) {if(dis[a[u]]+1==dis[now]&&val[u]){h=true;cur[now]=u;last[a[u]]=u;now=a[u];break;}u=nxt[u];}if(!h){int minn=n-1,u;u=p[now];while(u!=-1) {if(val[u]) minn=min(minn,dis[a[u]]);u=nxt[u];}--num[dis[now]];if(!num[dis[now]]) break;dis[now]=minn+1;num[minn+1]++;cur[now]=p[now];if(now!=s) now=a[last[now]^1];}}return sum;
}
int main()
{freopen("build.in","r",stdin);freopen("build.out","w",stdout);int i,j; tot=-1;memset(nxt,-1,sizeof(nxt));memset(p,-1,sizeof(p));scanf("%d%d%d",&n,&m,&id);for(i=1;i<=m;++i) scanf("%d%d%d",&d[i].s,&d[i].t,&d[i].v);int x=d[id].v;for(i=1;i<=m;++i)if(i!=id&&d[i].v<=x) add(d[i].s,d[i].t,x-d[i].v+1),add(d[i].t,d[i].s,x-d[i].v+1);ans=isap(d[id].s,d[id].t);printf("%d\n",ans);return 0;
}</strong>

这篇关于【bzoj 2521】 [Shoi2010] 最小生成树（网络流最小割）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---