扯在前面

人生第一道黑（>▽< )。

那天听了老师讲图论讲了这道题，发现这道黑题并不是很黑于是就做了做，在同机房dalao的帮助下三个小时做完（太菜了），于是来发篇题解。

正文

题意

给出一张 n 个点 m 条边的无向图，每条边(ai,bi)有一个权值 wi 和费用 ci，表示这条边每降低 1 的权值需要 ci 的花费。现在一共有 S 费用可以用来降低某些边的权值（可以降到负数），求图中的一棵权值和最小的生成树并输出方案

分析

本题就是一个求最小生成树加不定边的题目，而且输出多了个方案

题目中信息很多，在这里先总结一下：

最多降低权值为 S / ci;
既然你可以用 S 费用来降低 S / ci 的权值，而且可以降到负数，本题又是求最小生成树，那就一直降一条边就好了（保证降完后本条边是在生成树里的）；
他要求输出方案，就需要开数组或结构体来存储树上的是第几条边以及他的权值

好像就这么点信息也不是很多

那么我们想想该怎么做

我们知道，本题肯定是先求最小生成树，然后再枚举边看是否替换并比较最优方案；
枚举边有两种情况，第一是已经在生成树上的边，既然已经在树上，那么答案就直接把最小生成树权值和减去降低的权值拿来比较就好了
另一方面，最多减低 S / ci 的权值，那 ci 肯定越小越好，所以在树内的边我们就降低 c 最小的那一条
枚举数外的边时，我们要看加入当前边后是否为环（肯定是），把这条边与环上最大的树边比较，如果树边更大就减去这条树边（这个思路是不是有些熟悉）
当不用换边时，就直接输出原树的信息就好了

贴码

做的时候没写注释，但是很好理解，就是lca板子加编号和边权的存储，最后打个标记看是否换边

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<cmath>

#include<queue>

#include<algorithm>

#define maxn 200005

#define INF 1000000000000000000

using namespace std;

int n,m;

long long f[maxn][26],depth[maxn];

long long tot,head[maxn*4],fa[maxn],S,ans,num,cnt,sum,flag,lkp,fjh;

bool vis[maxn*2],v[maxn*2];

struct node{

	long long dis,c,fr,to,bh,nxt;

}a[maxn*4],e[maxn*4];

struct ma{

	long long dis,bh;

}maxi[maxn][26];

inline void add(long long fr,long long to,long long dis,long long c,long long bh){

	e[++tot].to=to;

	e[tot].fr=fr;

	e[tot].dis=dis;

	e[tot].bh=bh;

	e[tot].c=c;

	e[tot].nxt=head[fr];

	head[fr]=tot;

}

inline long long Getf(long long x){

	if(fa[x]==x) return x;

	return fa[x]=Getf(fa[x]);

}

inline void hb(long long x,long long y){

	x=Getf(x);

	y=Getf(y);

	if(x!=y) fa[y]=x;

}

inline bool pd(long long x,long long y){

	x=Getf(x);

	y=Getf(y);

	if(x==y) return true;

	return false;

}

inline void dfs(long long now,long long p){

	f[now][0]=p;

	for(long long i=head[now];i;i=e[i].nxt){

		long long to=e[i].to;

		if(to==f[now][0]) continue;

	    depth[to]=depth[now]+1ll;

		maxi[to][0].dis=e[i].dis;

		maxi[to][0].bh=e[i].bh;

		dfs(to,now);

	}

}

inline void caq(){

	for(int i=1;i<=25;++i)

		for(int j=1;j<=n;++j){

			f[j][i]=f[f[j][i-1]][i-1];//

//			maxi[j][i]=max(maxi[j][i-1],maxi[f[j][i-1]][i-1]);

//			mini[j][i]=max(mini[j][i-1],mini[f[j][i-1]][i-1]);

			if(maxi[j][i-1].dis>maxi[f[j][i-1]][i-1].dis){

			    maxi[j][i].dis=maxi[j][i-1].dis;

				maxi[j][i].bh=maxi[j][i-1].bh;

			}

            else{

			    maxi[j][i].dis=maxi[f[j][i-1]][i-1].dis;

            	maxi[j][i].bh=maxi[f[j][i-1]][i-1].bh;

		    }

		}

}

inline long long lca(long long x,long long y){

    if(depth[x]<depth[y]) swap(x,y);

//    while(depth[x]>depth[y])

//        x=f[x][lg[depth[x]-depth[y]]-1];

    for(int i=25;i>=0;--i)

		if(depth[f[x][i]]>=depth[y])

			x=f[x][i];

    if(x==y) return x;

    for(int i=25;i>=0;--i)

        if(f[x][i]!=f[y][i]){

            x=f[x][i];

            y=f[y][i];

        }

    return f[x][0];

}

inline ma get_max(long long u,long long v)

{

    ma Ans;

	Ans.bh=-1;

	Ans.dis=-INF;

	for(int i=25;i>=0;--i){

		if(depth[f[u][i]]>=depth[v]){

		    if(Ans.dis<maxi[u][i].dis){

		    	Ans.dis=maxi[u][i].dis;

		    	Ans.bh=maxi[u][i].bh;

			}

			u=f[u][i];

		}

	}

	return Ans;

}

inline long long cmp(node a,node b){

	return a.dis<b.dis;

}

int main(){

	cin>>n;cin>>m;

	for(int i=1;i<=m;i++) cin>>a[i].dis;

	for(int i=1;i<=m;i++) cin>>a[i].c;

	for(int i=1;i<=m;i++){

		cin>>a[i].fr;

		cin>>a[i].to;

		a[i].bh=i;

	}

	cin>>S;

	for(int i=1;i<=n;i++) fa[i]=i;

	sort(a+1,a+m+1,cmp);

	for(int i=1;i<=m;i++){

		if(!pd(a[i].fr,a[i].to)){

			hb(a[i].fr,a[i].to);

			add(a[i].fr,a[i].to,a[i].dis,a[i].c,i);

			add(a[i].to,a[i].fr,a[i].dis,a[i].c,i);

			sum+=a[i].dis;

			vis[i]=1;

			v[i]=1;

		}

	}

//	sort(e+1,e+m+1,cnp);

	depth[1] = 1;

	maxi[1][0].dis = -INF;

	maxi[1][0].bh = e[1].bh;

	dfs(1,1);

	caq();

	cnt=INF;

	for(long long i=1;i<=m;i++){

		long long ww=S/a[i].c;

		if(vis[i]){

			if(cnt>sum-ww){

			    flag=i;

			}

			cnt=min(sum-ww,cnt);

		}

		else{

			long long fr=a[i].fr;

			long long to=a[i].to;

			long long lcaa=lca(fr,to);

			ma maxu=get_max(fr,lcaa);

			ma maxv=get_max(to,lcaa);

			if(maxu.dis>maxv.dis){

				if(cnt>sum-maxu.dis+a[i].dis-ww){

					cnt=sum-maxu.dis+a[i].dis-ww;

					v[lkp]=0;

					v[fjh]=1;

					v[i]=1;

					v[maxu.bh]=0;

					lkp=i;

					fjh=maxu.bh;

					flag=i;

				}

			}

			else{

				if(cnt>sum-maxv.dis+a[i].dis-ww){

				    cnt=sum-maxv.dis+a[i].dis-ww;

				    v[lkp]=0;

				    v[fjh]=1;

				    v[i]=1;

				    v[maxv.bh]=0;

				    lkp=i;

				    fjh=maxv.bh;

				    flag=i;

				}

			}

		}

//	cout<<ww<<"  ";

	}

	if(flag)

		a[flag].dis=a[flag].dis-(S/a[flag].c);

	printf("%lld\n",cnt);

//	cout<<flag<<" ";

//	cout<<S/a[flag].c<<endl;

	for(int i=1;i<=m;i++)

		if(v[i]) printf("%lld %lld\n",a[i].bh,a[i].dis);

	return 0;

}

第一次A黑可能比较鸡冻，如果有什么不对的地方请及时告知我

巴特西

CF733F

扯在前面

正文

题意

分析

贴码

最新文章

热门文章