hdu4284 狀態壓縮dp

hdu4284 狀態壓縮dp

 

Problem Description 　　PP loves travel. Her dream is to travel around country A which consists of N cities and M roads connecting them. PP has measured the money each road costs. But she still has one more problem: she doesn't have enough money. So she must work during her travel. She has chosen some cities that she must visit and stay to work. In City_i she can do some work to earn Ci money, but before that she has to pay Di money to get the work license. She can't work in that city if she doesn't get the license but she can go through the city without license. In each chosen city, PP can only earn money and get license once. In other cities, she will not earn or pay money so that you can consider Ci=Di=0. Please help her make a plan to visit all chosen cities and get license in all of them under all rules above.
　　PP lives in city 1, and she will start her journey from city 1. and end her journey at city 1 too.

Input 　　The first line of input consists of one integer T which means T cases will follow.
　　Then follows T cases, each of which begins with three integers: the number of cities N (N <= 100) , number of roads M (M <= 5000) and her initiative money Money (Money <= 10^5) .
　　Then follows M lines. Each contains three integers u, v, w, which means there is a road between city u and city v and the cost is w. u and v are between 1 and N (inclusive), w <= 10^5.
　　Then follows a integer H (H <= 15) , which is the number of chosen cities.
　　Then follows H lines. Each contains three integers Num, Ci, Di, which means the i_th chosen city number and Ci, Di described above.(Ci, Di <= 10^5)

Output 　　If PP can visit all chosen cities and get all licenses, output YES, otherwise output NO.

Sample Input

2
4 5 10
1 2 1
2 3 2
1 3 2
1 4 1
3 4 2
3
1 8 5
2 5 2
3 10 1
2 1 100
1 2 10000
1
2 100000 1

Sample Output

YES
NO

/**
hdu4284  狀態壓縮dp
題目大意：給定一個城市網絡，要求從1出發在回到1，必須經過指定的一些點並在這些點中打工，打工可以掙一些路費，但是事先需要買許可證，問能否按照
          要求最終回到1點
解題思路：一開始以為是圖論題，想偏了== 指定的點最多有15個，我們可以用dp[st][j] 表示在st狀態下最終留在j點剩下的最多錢。floy預處理點與點之間
         的最短距離，然後狀態轉移即可。方程為：dp[s][i]=max(dp[s][i],dp[s'][j]-g[j][i]-d[i]+c[i]);
*/
#include 
#include 
#include 
#include 
using namespace std;
const int inf=0x3f3f3f3f;
int g[155][155];
int dp[1<<16][16];
int num[22],earn[22],cost[22];
int n,m,mon;
int main()
{
     int T;
     scanf(%d,&T);
     while(T--)
     {
         scanf(%d%d%d,&n,&m,&mon);
         memset(g,inf,sizeof(g));
         for(int i=1;i<=n;i++)
            g[i][i]=0;
         int a,b,c;
         while(m--)
         {
             scanf(%d%d%d,&a,&b,&c);
             if(c=0)///先初始化1到每個指定點
             {
                 dp[1<=0)
                     {
                         tmp+=earn[k];
                         int stat=i|(1<=0)
             {
                 flag=1;
                 break;
             }
         }
         if(flag)
            printf(YES
);
         else
            printf(NO
);
     }
     return 0;
}