HDU 4284 Travel 제3 7 회 ACM/ICPC 천진 지구 사 이 버 전 1007 문제(상태 압축 DP)
13619 단어 ICPC
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1380 Accepted Submission(s): 433
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
Source
2012 ACM/ICPC Asia Regional Tianjin Online
Recommend
liuyiding
비교적 간단 한데,주로 제목 의 뜻 을 잘 이해 해 야 한다.
1 시 에서 출발 하여 1 시 로 돌아 가 야 한다.H 개 점 을 거 쳐 야 하 는데 1 시 는 H 개 점 에 포 함 될 수도 있 고 포함 되 지 않 을 수도 있다.
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
#define INF 0x3f3f3f3f // ,
const int MAXN=150;
int dis[MAXN][MAXN];
int dp[20][1<<17];
struct Node
{
int num;
int C,D;
}node[20];
void floyed(int n)// 1~n
{
int i,j,k;
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(dis[i][j]>dis[i][k]+dis[k][j])
dis[i][j]=dis[i][k]+dis[k][j];
}
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int n,m;
int t;
int T;
int u,v,w;
int H;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&m,&t);
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
{
if(i==j)dis[i][j]=0;
else dis[i][j]=dis[j][i]=INF;
}
while(m--)
{
scanf("%d%d%d",&u,&v,&w);
if(w<dis[u][v])
dis[u][v]=dis[v][u]=w;
}
floyed(n);
scanf("%d",&H);
int start=-1;
for(int i=0;i<H;i++)
{
scanf("%d%d%d",&node[i].num,&node[i].C,&node[i].D);
if(node[i].num==1)start=i;
}
if(start==-1)
{
node[H].num=1;
node[H].C=node[H].D=0;
start=H;
H++;
}
for(int i=0;i<H;i++)
for(int j=0;j<(1<<H);j++)dp[i][j]=-INF;
// 1 licenses,
dp[start][0]=t;
if(t>=node[start].D)dp[start][1<<start]=t-node[start].D+node[start].C;
for(int j=0;j<(1<<H);j++)
for(int i=0;i<H;i++)//
{
if(dp[i][j]<0)continue;
for(int k=0;k<H;k++)
if(k!=i)
{
int t=(1<<k);
if((t&j)==0)
{
int temp;
if(dp[i][j]<dis[node[i].num][node[k].num])temp=-INF;
else
{
temp=dp[i][j]-dis[node[i].num][node[k].num];
if(temp<node[k].D)temp=-INF;
else temp+=node[k].C-node[k].D;
}
dp[k][t|j]=max(dp[k][t|j],temp);
}
}
}
bool flag=false;
int pp=(1<<H)-1;
for(int i=0;i<H;i++)
{
if(dp[i][pp]<0)continue;
if(dp[i][pp]>=dis[node[i].num][1])
{
flag=true;
break;
}
}
if(!flag)printf("NO
");
else printf("YES
");
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
2013 ACMICPC 항주 라이브 I 문제사고방식: 기억화 검색. dp[S]는 남은 상태가 S일 때 기수가 마법석을 최대 얼마나 얻을 수 있는지 나타낸다....
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.