HDU4966 GGS

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;
}