題目鏈接: (bzoj)https://www.lydsy.com/JudgeOnline/problem.php?id=4898

(luogu)https://www.luogu.org/problemnew/show/P3778

題解: 先Floyd求任意兩點最短路。

二分答案\(mid\)之后把邊權(quán)乘以\(mid\)判斷是否有大于\(0\)的即可。

\(O(n^2)\)枚舉每一對點，然后如果能實現(xiàn)從\(i\)點買入\(j\)點賣出，那么從\(i\)向\(j\)連邊代價為利潤減(最短路乘以\(mid\))。

然后直接在原圖上SPFA判正環(huán)即可。

時間復(fù)雜度\(O(ShortestPath(n,m+n^2)+n^3+n^2k)\)

自己還想到另一種做法就是設(shè)\(dp[i][j]\)為在\(i\)點持物品為\(j\)的最大利潤然后SPFA轉(zhuǎn)移，沒實現(xiàn)過。估計不可行，即使是對的也太慢。

代碼

#include<cstdio> #include<cstdlib> #include<cstring> #include<cassert> #include<algorithm> #define llong long long using namespace std;const int N = 100; const int M = 10000; const int P = 1000; const llong INF = 2000000000ll; struct AEdge {int u,v; llong w; } ae[M+3]; struct Edge {int v,nxt; llong w; } e[(M<<1)+3]; llong dist[N+3]; int que[N+3]; bool inq[N+3]; int tot[N+3]; bool vis[N+3]; int fe[N+3]; llong ai[N+3][P+3],ao[N+3][P+3]; llong mxv[N+3][N+3]; llong dis[N+3][N+3]; int n,m,p,en;void addedge(int u,int v,llong w) { // printf("addedge %d %d %lld\n",u,v,w);en++; e[en].v = v; e[en].w = w;e[en].nxt = fe[u]; fe[u] = en; }void clear() {for(int i=1; i<=n; i++) fe[i] = 0,vis[i] = false;for(int i=1; i<=en; i++) {e[i].v = e[i].w = e[i].nxt = 0;}en = 0; }bool spfa(int s) {for(int i=1; i<=n; i++) dist[i] = -INF,tot[i] = 0,inq[i] = false;int head = 1,tail = 2; que[tail-1] = s; dist[s] = 0ll; inq[s] = true; tot[s] = 1; vis[s] = true;while(head!=tail){int u = que[head]; head++; if(head>n+1) head = 1;for(int i=fe[u]; i; i=e[i].nxt){int v = e[i].v;if(dist[v]<=dist[u]+e[i].w){dist[v] = dist[u]+e[i].w;vis[v] = true;if(!inq[v]){que[tail] = v; tail++; if(tail>n+1) tail = 1;inq[v] = true; tot[v]++;if(tot[v]>n) return true;}}}inq[u] = false;}return false; }int main() {scanf("%d%d%d",&n,&m,&p);for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) dis[i][j] = INF;for(int i=1; i<=n; i++){for(int j=1; j<=p; j++){scanf("%lld%lld",&ai[i][j],&ao[i][j]);}}for(int i=1; i<=m; i++){scanf("%d%d%lld",&ae[i].u,&ae[i].v,&ae[i].w);dis[ae[i].u][ae[i].v] = ae[i].w;}for(int k=1; k<=n; k++){for(int i=1; i<=n; i++){for(int j=1; j<=n; j++){dis[i][j] = min(dis[i][j],dis[i][k]+dis[k][j]);}}} // for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) printf("dis[%d][%d]=%lld\n",i,j,dis[i][j]);for(int i=1; i<=n; i++){for(int j=1; j<=n; j++){mxv[i][j] = -INF;if(dis[i][j]){for(int k=1; k<=p; k++){if(ai[i][k]!=-1 && ao[j][k]!=-1) {mxv[i][j] = max(mxv[i][j],ao[j][k]-ai[i][k]);}}} // printf("mxv[%d][%d]=%lld\n",i,j,mxv[i][j]);}}llong left = 0ll,right = INF;while(left<right){llong mid = (left+right+1ll)>>1; // printf("left%lld right%lld mid%lld\n",left,right,mid);for(int i=1; i<=m; i++){addedge(ae[i].u,ae[i].v,-ae[i].w*mid);}for(int i=1; i<=n; i++){for(int j=1; j<=n; j++){if(mxv[i][j]>-INF) {addedge(i,j,mxv[i][j]-mid*dis[i][j]);}}}bool ok = false;for(int i=1; i<=n; i++){if(!vis[i]) {bool cur = spfa(i); if(cur) {ok = true; break;}}}if(ok) {left = mid;}else {right = mid-1;}clear();}printf("%lld\n",left);return 0; }

總結(jié)

以上是生活随笔為你收集整理的BZOJ 4898 Luogu P3778 [APIO2017]商旅 (分数规划、最短路)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。