HDU 4966 GGS - DDU (최소 트 리 맵 - 주유 알고리즘)

제목 주소: HDU 4966 은 처음에는 전체 등급 이 500 이라는 조건 을 제대로 보지 못 했 고 각각 500 으로 보 았 다.그리고 그림 을 만 들 면 생각 이 틀 렸 어 요...................................................알 고 보 니 모두 500 원 밖 에 없 었 습 니 다.그럼 건 도 는 간단 하 겠 네.각 과목 의 각 등급 을 하나의 점 으로 설정 하고 모든 0 등급 을 같은 나무 뿌리 로 설정 합 니 다.그 다음 에 모든 과목 의 높 은 등급 을 낮은 등급 으로 한 개의 가중치 가 0 인 방향 으로 연결 하 는 것 이다. 첫 번 째 역할 은 마지막 의 최소 트 리 그림 이 모든 점 에 달 할 수 있 도록 하 는 것 이다. 두 번 째 역할 은 매 수업 의 필요 한 등급 을 확보 하 는 것 이다. 높 은 등급 에 이 르 면 낮은 등급 도 일치 하도록 하 는 것 이다.그리고 매 수업 을 연결 하면 됩 니 다.코드 는 다음 과 같 습 니 다:

#include <iostream>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <map>
#include <set>
#include <stdio.h>
using namespace std;
#define LL __int64
#define pi acos(-1.0)
//#pragma comment(linker, "/STACK:1024000000")
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const double eqs=1e-9;
const int MAXN=40000+10;
int cnt, NV;
int in[510], color[510], id[510], pre[510], a[60], num[60];
struct node
{
        int u, v, w;
}edge[20000];
void add(int u, int v, int w)
{
        edge[cnt].v=v;
        edge[cnt].u=u;
        edge[cnt++].w=w;
}
int d_mst(int root)
{
        int ans=0, i, u, v;
        while(1){
                memset(in,INF,sizeof(in));
                for(i=0;i<cnt;i++){
                        u=edge[i].u;
                        v=edge[i].v;
                        if(u!=v&&edge[i].w<in[v]){
                                in[v]=edge[i].w;
                                pre[v]=u;
                        }
                }
                for(i=1;i<=NV;i++){
                        if(in[i]==INF&&i!=root) return-1;
                }
                int tot=0;
                memset(color,-1,sizeof(color));
                memset(id,-1,sizeof(id));
                in[root]=0;
                for(i=1;i<=NV;i++){
                        ans+=in[i];
                        u=i;
                        while(color[u]!=i&&id[u]==-1&&u!=root){
                                color[u]=i;
                                u=pre[u];
                        }
                        if(id[u]==-1&&u!=root){
                                id[u]=++tot;
                                for(v=pre[u];v!=u;v=pre[v]){
                                        id[v]=tot;
                                }
                        }
                }
                if(!tot) break;
                for(i=1;i<=NV;i++){
                        if(id[i]==-1) id[i]=++tot;
                }
                for(i=0;i<cnt;i++){
                        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].w-=in[v];
                        }
                }
                NV=tot;
                root=id[root];
        }
        return ans;
}
int main()
{
        int n, m, i, j, k, c, d, l1, l2, w, ans;
        while(scanf("%d%d",&n,&m)!=EOF&&n+m){
                num[0]=1;
                for(i=1;i<=n;i++){
                        scanf("%d",&a[i]);
                        num[i]=num[i-1]+a[i];
                }
                cnt=0;
                NV=num[n];
                for(i=1;i<=n;i++){
                        for(j=1;j<=a[i];j++){
                                add(num[i-1]+j,1,0);
                                for(k=1;k<j;k++){
                                        add(num[i-1]+j,num[i-1]+k,0);
                                }
                        }
                }
                while(m--){
                        scanf("%d%d%d%d%d",&c,&l1,&d,&l2,&w);
                        add(l1?num[c-1]+l1:1,l2?num[d-1]+l2:1,w);
                }
                ans=d_mst(1);
                printf("%d
",ans);
        }
        return 0;
}