2561: 最小生成树
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 1211 Solved: 585
[Submit][Status][Discuss]
Description
给定一个边带正权的连通无向图G=(V,E)，其中N=|V|，M=|E|，N个点从1到N依次编号，给定三个正整数u，v，和L (u≠v)，假设现在加入一条边权为L的边(u,v)，那么需要删掉最少多少条边，才能够使得这条边既可能出现在最小生成树上，也可能出现在最大生成树上？
Input
第一行包含用空格隔开的两个整数，分别为N和M；
接下来M行，每行包含三个正整数u，v和w表示图G存在一条边权为w的边(u,v)。
最后一行包含用空格隔开的三个整数，分别为u，v，和 L；
数据保证图中没有自环。
Output
输出一行一个整数表示最少需要删掉的边的数量。
Sample Input
3 2
3 2 1
1 2 3
1 2 2
Sample Output
1
HINT
对于20%的数据满足N ≤ 10，M ≤ 20，L ≤ 20；
对于50%的数据满足N ≤ 300，M ≤ 3000，L ≤ 200；
对于100%的数据满足N ≤ 20000，M ≤ 200000，L ≤ 20000。
Source
#include<cstdio>
#include<cstring>
#include<algorithm>
#define INF 1000000000
using namespace std;
struct node{int x,y,z;}ed[500010];
int n,m,edgenum,ans,source,sink,vs,x,y,z;
int vet[500010],next[500010],head[500010],maxv[500010],dis[500010],gap[500010];
bool cmp(node x,node y){return x.z<y.z;}
void add(int u,int v,int w)
{
vet[++edgenum]=v;
next[edgenum]=head[u];
head[u]=edgenum;
maxv[edgenum]=w;
}
int dfs(int u,int aug)
{
if (u==sink) return aug;
int mind=vs-1,flow=0;
for (int e=head[u];e;e=next[e])
{
if (maxv[e]<=0) continue;
int v=vet[e];
if (dis[u]==dis[v]+1)
{
int t=dfs(v,min(aug-flow,maxv[e]));
maxv[e]-=t;
if (e%2) maxv[e+1]+=t;else maxv[e-1]+=t;
flow+=t;
if (dis[source]>=vs) return flow;
if (aug==flow) break;
}
mind=min(mind,dis[v]);
}
if (!flow)
{
gap[dis[u]]--;
if (!gap[dis[u]]) dis[source]=vs;
dis[u]=mind+1;
gap[dis[u]]++;
}
return flow;
}
int maxflow(int s,int t,int n)
{
int ans=0;
memset(dis,0,sizeof(dis));
memset(gap,0,sizeof(gap));
source=s;sink=t;gap[0]=vs=n;
while (dis[source]<vs) ans+=dfs(source,INF);
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++) scanf("%d%d%d",&ed[i].x,&ed[i].y,&ed[i].z);
sort(ed+1,ed+m+1,cmp);
scanf("%d%d%d",&x,&y,&z);
for (int i=1;i<=m;i++)
if (ed[i].z>=z) break;else {add(ed[i].x,ed[i].y,1);add(ed[i].y,ed[i].x,1);}
ans=maxflow(x,y,n);
edgenum=0;memset(head,0,sizeof(head));
for (int i=m;i>=1;i--)
if (ed[i].z<=z) break;else {add(ed[i].x,ed[i].y,1);add(ed[i].y,ed[i].x,1);}
ans+=maxflow(x,y,n);
printf("%d\n",ans);
}
评论 (0)
