HDU 4966 GGS-DDU（最小树形图）

时间：2022-04-20 17:49:47

n个技能，每个技能有0～a[i]的等级，m个课程，每个课程需要前置技能c[i]至少达到lv1[i]等级，效果是技能d[i]达到lv2[i]等级，花费w[i]。

输出最小花费使得全技能满级（初始全技能0等级）

n<=50,Σa[i]<=500,m<=2000

点<=551,边<=2000+50+Σ((a[i]+1)*a[i]/2)

Σw[i]<=2000*1000<0x3f3f3f3f

比赛时候完全不在状态，什么题都想不到，坑队友了。。。

最小树形图～做过tarjan缩点的问题应该不大～以前做过不过好像没留下代码现在留下～

攻略步骤：

引用http://www.cnblogs.com/vongang/archive/2012/07/18/2596851.html

引用http://blog.csdn.net/wsniyufang/article/details/6747392

1、找到除了root以为其他点的权值最小的入边。用In[i]记录

2、如果出现除了root以为存在其他孤立的点，则不存在最小树形图。

3、找到图中所有的环，并对环进行缩点，重新编号。
4、更新其他点到环上的点的距离，如：

环中的点有（Vk1，Vk2，… ，Vki）总共i个，用缩成的点叫Vk替代，则在压缩后的图中，其他所有不在环中点v到Vk的距离定义如下：
gh[v][Vk]=min { gh[v][Vkj]-mincost[Vkj] } (1<=j<=i)

而Vk到v的距离为
gh[Vk][v]=min { gh[Vkj][v] }              (1<=j<=i)

5、重复3，4知道没有环为止。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

#define inf 0x3f3f3f3f

#define maxn 566

#define maxm (566*566+2000)

struct Edge{

	int u,v,w;

}e[maxm];

int in[maxn], pre[maxn];

int vis[maxn];

int belong[maxn];

int solve(int root,int n,int esz){// 1-based

	int ret=0;

	while(1){

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

		for(int i=1;i<=esz;++i){// 找最小边

			int u=e[i].u, v=e[i].v, w=e[i].w;

			if(v==u){

				swap(e[i--],e[esz--]);

				continue;

			}

			if(w<in[v])

				in[v]=w, pre[v]=u;

		}

		for(int i=1;i<=n;++i) if(in[i]==inf && i!=root) return inf;// 无解

		int cnt=0;

		memset(belong,-1,sizeof(belong));

		memset(vis,-1,sizeof(vis));

		in[root]=0;

		for(int i=1;i<=n;++i){// 找环

			ret+=in[i];

			int v = i;

			while(vis[v]!=i && belong[v]==-1 && v!=root)

				vis[v] = i, v = pre[v];

			if(vis[v]==i){// 有环，重新编号

				belong[v]=++cnt;

				for(int u=pre[v];u!=v;u=pre[u])

					belong[u]=cnt;

			}

		}

		if(cnt==0) break;// 已成型

		for(int i=1;i<=n;++i) if(belong[i]==-1) belong[i]=++cnt;// 不在环内，重新编号

		for(int i=1;i<=esz;++i){// 更新环外点和环缩点后的点的距离

			int v=e[i].v;

			e[i].u=belong[e[i].u];

			e[i].v=belong[e[i].v];

			if(e[i].u!=e[i].v) e[i].w-=in[v];

		}

		n=cnt;

		root=belong[root];

	}

	return ret;

}

int main(){

	int n,m;

	int a[55],s[55];

	while(~scanf("%d%d",&n,&m) && n+m){

		s[0]=1;

		for(int i=1;i<=n;++i) scanf("%d",a+i), s[i]=s[i-1]+a[i]+1;

		int esz=0;

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

			int c,l1,d,l2,w;

			scanf("%d%d%d%d%d",&c,&l1,&d,&l2,&w);

			int u=s[c-1]+l1+1, v=s[d-1]+l2+1;

			++esz;

			e[esz].u=u,e[esz].v=v,e[esz].w=w;

		}

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

			++esz;

			e[esz].u=1,e[esz].v=s[i-1]+1,e[esz].w=0;

			for(int j=0;j<=a[i];++j){

				for(int k=0;k<j;++k){

					int u=s[i-1]+j+1,v=s[i-1]+k+1;

					++esz;

					e[esz].u=u,e[esz].v=v,e[esz].w=0;

				}

			}

		}

		int ans=solve(1,s[n],esz);

		if(ans==inf) puts("-1");

		else printf("%d\n",ans);

	}

	return 0;

}

相关文章