problem：3169旅行

problem：3169旅行

問題描述：

某趟列車的最大載客容量為V人，沿途共有n個停靠站，其中始發站為第1站，終點站為第n站。在第1站至第n-1站之

間，共有m個團隊申請購票搭乘，若規定：（1）對于某個團隊的購票申請，要麼全部滿足，要麼全部拒絕，即不允

許隻滿足部分。（2）每個乘客的搭乘費用為其所乘站數。問：應如何選擇這些購票申請，能使該趟列車獲得最大

的搭乘費用？其中，每個團隊的購票申請格式是以空格分隔的三個整數：a b t，即表示有t個人需要從第a站點

乘至第b站點（注：每個團隊的所有人員都必須同時在a站上車，且必須同時在後面的b站下車）。

輸入

有若幹行。其中：

第1行隻有三個整數n，m，v，分别表示站點數、申請數、列車的最大載客容量。

這三個整數之間都以一個空格分隔。

第2行至第m+1行，每行有三個整數，中間都以一個空格分隔。

其中第k+1行的三個整數a，b，t表示第k個申請，含義為：有t個人需要從第a站乘至第b站。

1≤n≤10；1≤m≤18，1<=V<=200

輸出

隻有一行，該行隻有一個整數，為該列車能獲得的最大搭乘費用。

樣例輸入：

3 3 5

1 2 2

2 3 5

1 3 4

樣例輸出：

8

//當隻選擇第3個申請時，能獲得的最大搭乘費用為（3-1）*4=8

#include <bits/stdc++.h>
#define maxn 19
int n,m,v,ans;
int chafen[maxn],a[maxn],b[maxn],t[maxn];
bool exsit[maxn];

using namespace std;
bool cheak(){//判斷是否超載 
    int total=;
    for(int i=;i<=n;i++){
        total+=chafen[i];
        if(total>v)return ; 
    }
    return ;
}

void dfs(int dep){//每個站點都是上或不上人，總共2^m種方案
    if(dep==m+){
        for(int i=;i<=n;i++) chafen[i]=;//初始化
        int temp=;
        for(int i=;i<=m;i++)
            if(exsit[i]){
                chafen[a[i]]+=t[i];//構造括号序列
                chafen[b[i]]-=t[i];
                temp+=(b[i]-a[i])*t[i];//計算目前方案總價錢 
             } 
         if(cheak())ans=max(ans,temp);//統計最大價錢
         return; 
    } 
    dfs(dep+);
    exsit[dep]=;//1代表上
    dfs(dep+);
    exsit[dep]=;//0代表不上
}

int main(){
    scanf("%d%d%d",&n,&m,&v);
    for(int i=;i<=m;i++)
        scanf("%d%d%d",&a[i],&b[i],&t[i]);
    dfs();
    printf("%d\n",ans);
}