蜀传之单刀赴会

xiaoxiao2021-02-28  87

题目描述 【题目背景】

公元215年,刘备取益州,孙权令诸葛瑾找刘备索要荆州。刘备不答应,孙权极为恼恨,便派吕蒙率军取长沙、零陵、桂阳三郡。长沙、桂阳蜀将当即投降。刘备得知后,亲自从成都赶到公安(今湖北公安),派大将关羽争夺三郡。孙权也随即进驻陆口,派鲁肃屯兵益阳,抵挡关羽。双方剑拔弩张,孙刘联盟面临破裂,在这紧要关头,鲁肃为了维护孙刘联盟,不给曹操可乘之机,决定当面和关羽商谈。“肃邀羽相见,各驻兵马百步上,但诸将军单刀俱会”。双方经过会谈,缓和了紧张局势。随后,孙权与刘备商定平分荆州,“割湘水为界,于是罢军”,孙刘联盟因此能继续维持。

【问题描述】

关羽受鲁肃邀请,为了大局,他决定冒险赴会。他带着侍从周仓,义子关平,骑着赤兔马,手持青龙偃月刀,从军营出发了,这就是历史上赫赫有名的“单刀赴会”。关羽平时因为军务繁重,决定在这次出行中拜访几个多日不见的好朋友。然而局势紧张,这次出行要在限定时间内完成,关公希望你能够帮助他安排一下行程,安排一种出行方式,使得从军营出发,到达鲁肃处赴会再回来,同时拜访到尽可能多的朋友,在满足这些条件下行程最短。注意拜访朋友可以在赴会之前,也可以在赴会之后。现在给出地图,请你完成接下来的任务。

输入 第一行n,m,k,t,代表有n个地点,m条道路,有k个朋友(不包括鲁肃),以及限定时间t(行走1单位长度的路程用时1单位时间)。

接下来m行,每行有x,y,w三个整数,代表x和y之间有长度为w的道路相连。 接下来一行有k个整数,代表朋友所在的都城编号(保证两两不同,且不在1和n)

(我们约定1是关羽的营地,n是鲁肃的营地)

输出 输出两个整数,分别是最多可以拜访的朋友数,以及在这种情况下最少需要耗费的时间,如果连到达鲁肃再回来都无法完成,输出一个-1就可以了。

样例输入 5 7 2 15 1 2 5 1 3 3 2 3 1 2 4 1 3 4 4 2 5 2 4 5 3 2 4 样例输出 2 14 提示 【数据规模和约定】

有10%数据,n<=10,m<=50,k<=5;

有10%数据,k=0;

有10%数据,k=1;

另30%数据,k<=5;

对于100%数据,n<=10000,m<=50000,k<=15,t<=2147483647,w<=10000

题解 水一发状压DP。利用dijkstra处理处朋友两两间的最短距离,然后就是水状压。。

代码

#include<bits/stdc++.h> #define pa pair<int,int> #define inf 1000000000005 #define N 10005 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int tot,n,m,k,t; ll f[1<<18][18],dis[N],d[20][20]; int Head[N],ret[N*10],Next[N*10],len[N*10],p[18]; bool vis[N]; inline void ins(int u,int v,int l) { ret[++tot]=v;len[tot]=l; Next[tot]=Head[u];Head[u]=tot; } void dijkstra(int u) { priority_queue<pa,vector<pa>,greater<pa> >q; for (int i=1;i<=n;i++) dis[i]=inf,vis[i]=0; dis[u]=0;q.push(make_pair(0,u)); while (!q.empty()) { int now=q.top().second;q.pop(); if (vis[now]) continue;vis[now]=1; for (int i=Head[now];i;i=Next[i]) if (dis[now]+len[i]<dis[ret[i]]) { dis[ret[i]]=dis[now]+len[i]; q.push(make_pair(dis[ret[i]],ret[i])); } } } int count(int i) { int ans=0; while (i) { if (i&1) ans++; i>>=1; } return ans; } int main() { n=read(),m=read(),k=read(),t=read(); for (int i=1;i<=m;i++) { int u=read(),v=read(),t=read(); ins(u,v,t);ins(v,u,t); } for (int i=1;i<=k;i++) p[i]=read(); k++;p[k]=n;p[0]=1; for (int i=0;i<=k;i++) { dijkstra(p[i]); for (int j=0;j<=k;j++) d[i][j]=dis[p[j]]; } int all=1<<k; memset(f,127,sizeof(f)); for (int i=1;i<=k;i++) f[1<<(i-1)][i]=d[0][i]; for (int i=1;i<all;i++) for (int j=1;j<=k;j++) if (i&(1<<(j-1))) { for (int l=1;l<=k;l++) { if (i&(1<<(l-1))) continue; f[i|(1<<(l-1))][l]=min(f[i|(1<<(l-1))][l],f[i][j]+d[j][l]); } } int ans1=0,ans2; for (int i=1;i<=all;i++) { int num=count(i); if (num<ans1) continue; if (!(i&(1<<(k-1)))) continue; for (int j=1;j<=k;j++) if (i&(1<<(j-1))) { if (num>ans1&&f[i][j]+d[j][0]<=t) { ans1=num;ans2=f[i][j]+d[j][0]; } else if (num==ans1&&f[i][j]+d[j][0]<=t) ans2=(int)min((ll)ans2,f[i][j]+d[j][0]); } } if (ans1==0) puts("-1"); else printf("%d %d",ans1-1,ans2); return 0; }
转载请注明原文地址: https://www.6miu.com/read-78004.html

最新回复(0)