Hdu 3810 Magina(DP_リュック)

タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=3810
最后の段阶はやっとn山の野獣があると言って、すべての野獣が屠杀し终わってti时间を费やして、金giを増加することができて、敌の法师は瞬移の技能があって、ある山の野獣から别の山の野獣に移动することができて、テーマはどの山からどの山に移动することができます.最後に、お金が足りない場合の最低時間を聞いてみます.
2011年武漢招待試合のネット試合の金メダル問題、テーマは複雑に見えて、またn山の獣で、また各種の瞬時移動です.しかし、理がはっきりした后にこれがリュックサックの问题であることを発见して、まずつながっている獣の山を深く探し出して1组にまとめて、それから私达がしなければならないのはこの组の中で0,1,...num[tot]の山を选んで屠杀して、すべての獣は2种类の选択があります:杀して杀しますか?このように问题はtot组01リュックサックを求めます.
     しかし、本題の金銭と虐殺時間の範囲は特に大きく、虐殺時間の範囲は1-1000万人で、金銭の範囲は1-10億人で、通常の2重循環シミュレーションではできない.実は2つの優先キューで01リュックの計算過程をシミュレートすることができて、初めて(0,0)を入隊して、それから次の状態に移動して、この2つの状態を移動してすべてキューに入って、2つの優先キューで操作することができて、1つは前のラウンドの計算結果を表して、1つはこのラウンドで、スクロール配列に相当します.優先キューシミュレーションの過程で枝切りに注意し、切らないかよく切らないとMLEです.私はいくつかの枝を切ってみましたが、一つだけいいです.それは、移動が終わるたびにキュー1をキュー2にコピーするときに、入隊したこの点が前の入隊の点よりも価値が少なく、時間が少ないかどうかを判断することです.そうでなければ、これは前の入隊の方が優れているに違いありません.例えば、(6,4)はお金が6で、時間が4かかります.次のチームに入るのが(5,5)なら、前のほうが優れているに違いありません.そうです.
    この問題はまた、出力が不可能な場合に++Casを少なく書いたため、Waが何度か書きました.前はずっとMLEで、後ろはWaで、アルゴリズムの問題だと思って、ずっとアルゴリズムをチェックしています.このような状況は現場試合でも遭遇する可能性があると思いますが、今出会ったのはいいことだと思います.万年船に気をつけてください.
   私のようにiSeaのスケジュールより15倍速く書いて、1位は、強く切って力強くて、瑟下しなければなりません.   
テストデータ:

  
10 3 9 3 3 2 2 3 3 3 2 1 3 3 3 2 1 2   3 3 3 3 2 2 3 5 3 2 1 3 4 3 2 1 2  1 4 2 5 0  1 5 1 4 0  4 10 1 9 0 3 3 1 3 3 3 2 2 4 4 4 1 3 
コード:
#include <stdio.h>
#include <string.h>
#include <queue>
#include <string.h>
using namespace std;
#define MIN 52
#define INF 1000000000
#define int64 __int64


struct node {

    int64 t,val;
    friend int operator < (node a,node b) {

		if (a.val == b.val)
			return a.t > b.t;
		else
			return a.val < b.val;
    }
}arr[MIN],now,next;
priority_queue<node> qu1,qu2;
int n,m,maze[MIN][MIN],vis[MIN];
int gtot,num[MIN],group[MIN][MIN];


void Dfs(int i) {

    vis[i] = 1;
    int j = ++num[gtot];
    group[gtot][j] = i;
    for (int k = 1; k <= n; ++k)
        if (!vis[k] && maze[i][k]) Dfs(k);
}
void DivideGroup() {

    int i,j,k;
    for (gtot = i = 1; i <= n; ++i)
        if (!vis[i]) Dfs(i),gtot++;
}
int64 Solve_1A() {

    int i,j,k;
    int64 minn,tpk,tpval;
    minn = INF;        //     1000  * 50 == 5 ， 10    


    for (i = 1; i < gtot; ++i) {
    //  01  
        while (!qu1.empty()) qu1.pop();
        while (!qu2.empty()) qu2.pop();
        now.t = now.val = 0;
        qu1.push(now);


        for (j = 1; j <= num[i]; ++j) {

            k = group[i][j];        //group        
            while (!qu1.empty()) {

                now = qu1.top();
				qu1.pop(),qu2.push(now);
				next.t = now.t + arr[k].t;
                next.val = now.val + arr[k].val;
                   

                if (next.val >= m) {

                    if (next.t < minn) minn = next.t;
                    continue;
                }
				if (next.t >= minn) continue;
				qu2.push(next);
            }


			tpk = INF;
            while (!qu2.empty()) {
					
                now = qu2.top(),qu2.pop();
                if (tpk >= now.t) qu1.push(now),tpk = now.t;//   val      ，           ，     
            }
        }
    }
    return minn == INF ? -1 : minn;
}


int main()
{
    int i,j,t,cas = 0;
    int u,v,k;


    scanf("%d",&t);
    while (t--) {

        scanf("%d%d",&n,&m);
        memset(maze,0,sizeof(maze));
        memset(vis,0,sizeof(vis));
        memset(num,0,sizeof(num));
        for (i = 1; i <= n; ++i) {

            scanf("%d%d%d",&arr[i].t,&arr[i].val,&k);
            while (k--) {

                scanf("%d",&u);
                maze[i][u] = 1;
            }
        }


        DivideGroup();   //          
        int64 ans = Solve_1A();
        if (ans != -1) printf("Case %d: %I64d
",++cas,ans);
        else printf("Case %d: Poor Magina, you can't save the world all the time!
",++cas);
    }
}
  
 ZeroClockオリジナルですが、  できます. たちは  だからです.