點擊打開鏈接
題意：給個n行m列的數列，一個人可以走k次，每次選擇一個未走過的點，這個點繼續走的話，可以往下走或往右走，當然他可以跳著走，也就是可以跳到下面或右面任意一個位置，但前提是這個點沒有走過，初始能量為0，從a，b走到c，d消耗能量是|a-c|+|b-d|-1；問走K次能否將所有點走到，並且每個點只能走一次，，成功的話輸出最後可以剩下的最多能量
思路：先要處理k次能否成功，想到了最小路徑覆蓋=定點數-最大匹配，那麼最小路徑覆蓋的意義就是最小找幾個頂點開始跑才可以使路徑全被覆蓋，也就是所有點被覆蓋，剛剛好與此題相似，粘好最小路徑覆蓋模版，看下面，妹的，竟然是費用流，那這麼寫好像太麻煩了，想了想也不知道如何在費用流判斷這個k路徑覆蓋，看了官方題解，感覺智商不夠用啊，只要在二分圖的X部分再加一個邊，然後源點到這個點容量為k，費用為0，這個點到Y部所有點容量為1，費用為0；中間可以到達的點就連邊，費用為得到的能量-消耗的能量，然後求完備匹配的最大權就行了，最大權的求法點這裡
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int maxn=1010;
typedef pair P;
struct edge{
int to,cap,cost,rev;
edge();
edge(int a,int b,int c,int d){to=a,cap=b,cost=c,rev=d;};
};
vectorG[maxn];
int h[maxn],dis[maxn],prevv[maxn],preve[maxn];
void addedge(int st,int en,int cap,int cost){
G[st].push_back(edge(en,cap,cost,G[en].size()));
G[en].push_back(edge(st,0,-cost,G[st].size()-1));
}
int min_cost_flow(int st,int en,int f){
int ans=0;
memset(h,0,sizeof(h));
while(f>0){
priority_queue,greater >que;
memset(dis,inf,sizeof(dis));
dis[st]=0;que.push(P(0,st));
while(!que.empty()){
P p=que.top();que.pop();
int v=p.second;
if(dis[v]0&&dis[e.to]>dis[v]+e.cost+h[v]-h[e.to]){
dis[e.to]=dis[v]+e.cost+h[v]-h[e.to];
prevv[e.to]=v;
preve[e.to]=i;
que.push(P(dis[e.to],e.to));
}
}
}
if(dis[en]==inf) return -1;
for(int i=0;i
