題目鏈接：點(diǎn)擊查看

題目大意：給出一個(gè)區(qū)間，初始時(shí)為 [ 1 , n ] ，每次操作可以將 [ l , r ] 變?yōu)橄旅娴钠渲兄?#xff1a;

[ l + 1 , r ]

[ l , r - 1 ]

[ l - 1 , r ]

[ l , r + 1 ]

現(xiàn)在給出 m 次限制，表示可以花費(fèi)一定的代價(jià)，使得上述的前兩種或者后兩種變化無(wú)效，問(wèn)是否可以通過(guò)一些限制，使得永遠(yuǎn)無(wú)法達(dá)到 l == r 的狀態(tài)

題目分析：設(shè)源點(diǎn)為點(diǎn) ( 1 , n ) ，所有的 l == r 的點(diǎn)與匯點(diǎn)相連，不難看出，對(duì)于此圖求最大流最小割顯然是正確答案

因?yàn)辄c(diǎn)數(shù)較多，所以考慮轉(zhuǎn)換為對(duì)偶圖優(yōu)化，此類(lèi)問(wèn)題可以參考：狼抓兔子

轉(zhuǎn)換為對(duì)偶圖后，直接跑最短路就是答案了，記得開(kāi) long long ，我的建圖方法如下：

其中：淺藍(lán)色代表原來(lái)的點(diǎn)，紅色代表原來(lái)的邊（不屬于 m 條邊中的其他邊都賦值為 inf 即可），深藍(lán)色的為對(duì)偶圖的點(diǎn)，紫色的為對(duì)偶圖的邊?

代碼：
?

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> using namespace std;typedef long long LL;typedef unsigned long long ull;const LL inf=0x3f3f3f3f3f3f3f3f;const int N=3e5+100;//頂點(diǎn)數(shù) const int M=N*8;//邊數(shù) struct Edge {int to,next;LL w; }edge[M];int head[N],cnt,n,m,id[510][510];//鏈?zhǔn)角跋蛐荓L d[N],L[510][510],R[510][510]; bool vis[N];void addedge(int u,int v,LL w) {edge[cnt].to=v;edge[cnt].w=w;edge[cnt].next=head[u];head[u]=cnt++;edge[cnt].to=u;edge[cnt].w=w;edge[cnt].next=head[v];head[v]=cnt++; }struct Node {int to;LL w;Node(int TO,LL W){to=TO;w=W;}bool operator<(const Node& a)const{return w>a.w;} };void Dijkstra(int st) {priority_queue<Node>q;memset(vis,false,sizeof(vis));memset(d,0x3f,sizeof(d));d[st]=0;q.push(Node(st,0));while(q.size()){Node cur=q.top();int u=cur.to;q.pop();if(vis[u])continue;vis[u]=true;for(int i=head[u];i!=-1;i=edge[i].next)//掃描出所有邊 {int v=edge[i].to;LL w=edge[i].w;if(d[v]>d[u]+w)//更新 {d[v]=d[u]+w;q.push(Node(v,d[v]));}}} }void init() {memset(head,-1,sizeof(head));cnt=0;int tot=0;for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++){id[i][j]=++tot;L[i][j]=R[i][j]=inf;} }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);scanf("%d%d",&n,&m);init();int st=N-1,ed=st-1;while(m--){int l,r,w;char op[5];scanf("%d%d%s%d",&l,&r,op,&w);if(op[0]=='L')L[l][r]=w;elseR[l][r]=w;}for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++){if(i==1)addedge(st,id[i][j],R[i][j]);elseaddedge(id[i-1][j],id[i][j],R[i][j]);if(j==n)addedge(id[i][j],ed,L[i][j]);elseaddedge(id[i][j+1],id[i][j],L[i][j]);}Dijkstra(st);if(d[ed]==inf)puts("-1");elseprintf("%lld\n",d[ed]);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的牛客多校2 - Interval(网格图最大流转换为对偶图最短路)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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