GGS"/>
HDU4966 GGS
题意:有许多门课,每门课有不同的境界,一开始都在level 0,这小伙想参加一些补习班,使自己每门课的境界达到最高。补习班,在A课达到L1及以上,才能参加,修完后B课将达到L2 (Don't ask me why! Supernatural class!!!)
思路:把每门课的每一层境界看成一个点,建一个超级根,连接到每门课的level 0,每门课的高境界依次连到上一层境界,这样达到高境界后,低境界自然达到了,也能去参加低境界连过去的补习班了。
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<stdlib.h>
#include<math.h>
#include<vector>
#include<list>
#include<map>
#include<stack>
#include<queue>
#include<algorithm>
#include<numeric>
#include<functional>
using namespace std;
typedef long long ll;
const int maxn = 3505;
const int maxm = 30005;struct Edge
{int u, v; int cost;
}edge[maxm];//边集 int pre[maxn],id[maxn],vis[maxn];
int in[maxn];int zhuliu(int root,int n,int m)//返回最小花费
{ int res=0; while(true) { for(int i=0;i<n;++i) in[i]=0x3f3f3f3f; for(int i=0;i<m;++i) if(edge[i].u!=edge[i].v && edge[i].cost < in[edge[i].v]) { pre[edge[i].v]=edge[i].u; in[edge[i].v]=edge[i].cost;//if(edge[i].u == root) ansi = i; //无固定根,记录边} for(int i=0;i<n;++i) if(i!=root && in[i]==0x3f3f3f3f) return -1;//不存在最小树形图 int tn=0;//新图结点数 for(int i=0;i<n;++i) { id[i]=-1; vis[i]=-1; } in[root]=0; for(int i=0;i<n;++i) { res+=in[i]; int v=i; while(vis[v]!=i&&id[v]==-1&&v!=root) { vis[v]=i; v=pre[v]; } if(v!=root&&id[v]==-1) { for(int u=pre[v];u!=v;u=pre[u]) id[u]=tn; id[v]=tn++; } } if(tn==0)//没有有向环 break; for(int i=0;i<n;++i) if(id[i]==-1) id[i]=tn++; for(int i=0;i<m;i++) { int v=edge[i].v; edge[i].u=id[edge[i].u]; edge[i].v=id[edge[i].v]; if(edge[i].u!=edge[i].v) edge[i].cost-=in[v];} n=tn;root=id[root]; } return res;
} //点、边下标从0开始 //无固定根,加一点,边权sum+1,记录哪条边,推出哪个点void add(int i,int a,int b,int c)
{edge[i].u = a;edge[i].v = b;edge[i].cost = c;
}int main(void)
{int n,m;int sum[55];while(scanf("%d%d",&n,&m)!=EOF && n+m){sum[0] = 1;for(int i = 1; i <= n; i++){scanf("%d",&sum[i]);sum[i]++;sum[i] += sum[i-1];}int tp = 0;for(int i = 0; i < m; i++){int a,b,c,d,e;scanf("%d%d%d%d%d",&a,&b,&c,&d,&e);add(tp++,sum[a-1]+b,sum[c-1]+d,e);}for(int i = 0; i < n; i++)add(tp++,0,sum[i],0);for(int i = 1; i <= n; i++){for(int j = 0; j < sum[i]-sum[i-1]-1; j++)add(tp++,sum[i-1]+j+1,sum[i-1]+j,0);}int ans = zhuliu(0,sum[n],tp);printf("%d\n",ans);}return 0;
}
更多推荐
HDU4966 GGS
发布评论