[luoguP4142]洞穴遇險

https://www.zybuluo.com/ysner/note/1240792

題面

戳我

解析

這種用來拼接的奇形怪狀的東西,要不就是輪廓線\(DP\),要不就是網絡流。

為了表示奇數點(即\((x+y)\%2=1\))的危險值,把該點拆為兩個點,連一條邊長為該點危險值相反數的邊(兩點分別稱為起點和終點)。

鑒于一根柱子跨越\(3\)個格子,其中一點為奇數點,另外兩個點都是偶數點,不能區分。

于是也要把偶數點分為兩類(不用拆點)。一類連源點,一類連匯點。連匯點的一類連奇數點的起點,另一類連終點。(讓源點出發能到匯點就成)

然后思考如何表示柱子。

如果強行給柱子規定方向,則有\(8\)個方向。
表示出來,有兩種情況,一是\(x\)軸方向出,\(y\)軸方向進;另一種是\(y\)軸方向進,\(x\)軸方向出。
于是兩個奇數點分別反映一種情況,同時注意相鄰的偶數點連奇數點中的起點、還是終點即可。

還要注意的是,最小費用最大流模板求出的是在最大流前提下的最小流,在后期,可能為了得到最大流而付出更多費用(在本題中就是為了放更多柱子而增加不穩定度)。在費用開始非負時(開始退流時)記得\(break\)

唯一一種能讓網絡流TLE的方式就是cnt=0

// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#define re register
#define il inline
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int mod=1e9+7,N=5e3+100;
struct Edge{int to,nxt,w,c;}e[N*10];
int n,m,k,s,sum,h[N],d[55][55],ans=0,dis[N],S,T,pe[N],pv[N],tot,cnt=1,g;
bool vis[N],ban[55][55];
il void add(re int u,re int v,re int w,re int c)
{if(u==-1||v==-1) return ;e[++cnt]=(Edge){v,h[u],w,c};h[u]=cnt;e[++cnt]=(Edge){u,h[v],0,-c};h[v]=cnt;
}
queue<int>Q;
il ll gi()
{re ll x=0,t=1;re char ch=getchar();while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();if(ch=='-') t=-1,ch=getchar();while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();return x*t;
}
il int id(re int x,re int y){return (x-1)*n+y;}
il int SPFA()
{memset(dis,63,sizeof(dis));dis[S]=0;vis[S]=1;Q.push(S);while(!Q.empty()){re int u=Q.front();Q.pop();for(re int i=h[u];i+1;i=e[i].nxt){re int v=e[i].to;//printf("!!!%d %d\n",u,v);if(dis[v]>dis[u]+e[i].c&&e[i].w){dis[v]=dis[u]+e[i].c;pe[v]=i;pv[v]=u;if(!vis[v]) vis[v]=1,Q.push(v);}}vis[u]=0;}return dis[T]<dis[0];
}
int main()
{//freopen("marshland.in","r",stdin);//freopen("marshland.out","w",stdout);memset(h,-1,sizeof(h));n=gi();m=gi();k=gi();g=n*n;S=2*g+1;T=2*g+2;fp(i,1,n)fp(j,1,n)d[i][j]=gi(),s+=d[i][j];fp(i,1,k){re int u=gi(),v=gi();ban[u][v]=1;}fp(i,1,n)fp(j,1,n){if(ban[i][j]) continue;if((i+j)%2) add(id(i,j),id(i,j)+g,1,-d[i][j]);if((i+j)%2&&j%2==0){if(i>1&&!ban[i-1][j]) add(id(i,j)+g,id(i-1,j),1,0);if(i<n&&!ban[i+1][j]) add(id(i,j)+g,id(i+1,j),1,0);if(j>1&&!ban[i][j-1]) add(id(i,j-1),id(i,j),1,0);if(j<n&&!ban[i][j+1]) add(id(i,j+1),id(i,j),1,0);}if((i+j)%2&&j%2==1){if(i>1&&!ban[i-1][j]) add(id(i-1,j),id(i,j),1,0);if(i<n&&!ban[i+1][j]) add(id(i+1,j),id(i,j),1,0);if(j>1&&!ban[i][j-1]) add(id(i,j)+g,id(i,j-1),1,0);if(j<n&&!ban[i][j+1]) add(id(i,j)+g,id(i,j+1),1,0);}if((i+j)%2==0&&j%2==1) add(S,id(i,j),1,0);if((i+j)%2==0&&j%2==0) add(id(i,j),T,1,0);}while(SPFA()&&m){if(dis[T]>=0) break;sum=2e9;for(re int i=T;i!=S;i=pv[i])sum=min(sum,e[pe[i]].w);m-=sum;//printf("%d\n",sum);for(re int i=T;i!=S;i=pv[i])e[pe[i]].w-=sum,e[pe[i]^1].w+=sum,ans+=sum*e[pe[i]].c;}printf("%d\n",s+ans);fclose(stdin);fclose(stdout);return 0;
}

轉載于:https://www.cnblogs.com/yanshannan/p/9433035.html

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/388891.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/388891.shtml
英文地址,請注明出處:http://en.pswp.cn/news/388891.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

飛信虛擬機

做完了一個圖片處理軟件,突然想到上次上網看到C#程序脫離.NET FRAMEWORK運行的文章,于是決定自己動手試一下。 之前看到有用別的方法來實現的&#xff0c;但我還是選擇了現在比較流行的軟件飛信中帶的VMDotNet&#xff0c;也就是所謂的.NET FRAMEWORK虛擬機吧。相信有很多人也已…

django的contenttype表

https://blog.csdn.net/aaronthon/article/details/81714496 這篇文章已經非常詳細了,供自己以后忘了...回看...... 總結&#xff1a; 當一張表和多個表FK關聯&#xff0c;并且多個FK中只能選擇其中一個或其中n個時&#xff0c;可以利用contenttype&#xff0c;固定用三個字段…

視頻播放問題和提高性能方案

1.Five symptoms of poor video performance 1.1 視頻加載緩慢 ?Perceived Wait Time Time to first frame (TTFF): ? 播放開始所需的adaptive bitrate(ABR)流媒體段的數量。(我們稍后將對此進行更詳細的討論。) ? 視頻請求發送到視頻加載之間的時間(即接收到足夠的數據…

rabbitmq 不同的消費者消費同一個隊列_RabbitMQ 消費端限流、TTL、死信隊列

消費端限流1. 為什么要對消費端限流假設一個場景&#xff0c;首先&#xff0c;我們 Rabbitmq 服務器積壓了有上萬條未處理的消息&#xff0c;我們隨便打開一個消費者客戶端&#xff0c;會出現這樣情況: 巨量的消息瞬間全部推送過來&#xff0c;但是我們單個客戶端無法同時處理這…

動量策略 python_在Python中使用動量通道進行交易

動量策略 pythonMost traders use Bollinger Bands. However, price is not normally distributed. That’s why only 42% of prices will close within one standard deviation. Please go ahead and read this article. However, I have some good news.大多數交易者使用布林…

css3 變換、過渡效果、動畫

1 CSS3 選擇器 1.1 基本選擇器 1.2 層級 空格 > .itemli ~ .item~p 1.3 屬性選擇器 [attr] [attrvalue] [attr^value] [attr$value] [attr*value] [][][] 1.4 偽類選擇器 :link :visited :hover :active :focus :first-child .list li:first-child :last-chi…

webservice 啟用代理服務器

您會發現你寫完了一個webservice在調用的時候發現怎也沒辦法調用&#xff0c;一個簡單的webservice怎么不能使用&#xff0c;一肚子的怨恨&#xff0c;哈哈您可能沒有為webservice設置代理。 下面就給您寫個調用的用例和大家分享下。其實很簡單&#xff0c;但是你沒有想到的時…

mysql常用的存儲引擎_Mysql存儲引擎

什么是存儲引擎&#xff1f;關系數據庫表是用于存儲和組織信息的數據結構&#xff0c;可以將表理解為由行和列組成的表格&#xff0c;類似于Excel的電子表格的形式。有的表簡單&#xff0c;有的表復雜&#xff0c;有的表根本不用來存儲任何長期的數據&#xff0c;有的表讀取時非…

android studio設計模式和文本模式切換

轉載于:https://www.cnblogs.com/judes/p/9437104.html

高斯模糊為什么叫高斯濾波_為什么高斯是所有發行之王?

高斯模糊為什么叫高斯濾波高斯分布及其主要特征&#xff1a; (Gaussian Distribution and its key characteristics:) Gaussian distribution is a continuous probability distribution with symmetrical sides around its center. 高斯分布是連續概率分布&#xff0c;其中心周…

C# webbrowser 代理

百度&#xff0c;google加自己理解后&#xff0c;將所得方法總結一下&#xff1a; 方法1&#xff1a;修改注冊表Software//Microsoft//Windows//CurrentVersion//Internet Settings下 ProxyEnable和ProxyServer。這種方法適用于局域網用戶&#xff0c;撥號用戶無效。 1p…

C MySQL讀寫分離連接串_Mysql讀寫分離

一 什么是讀寫分離MySQL Proxy最強大的一項功能是實現“讀寫分離(Read/Write Splitting)”。基本的原理是讓主數據庫處理事務性查詢&#xff0c;而從數據庫處理SELECT查詢。數據庫復制被用來把事務性查詢導致的變更同步到集群中的從數據庫。當然&#xff0c;主服務器也可以提供…

golang 編寫的在線redis 內存分析工具 rma4go

redis 內存分析工具 rma4go redis是一個很有名的內存型數據庫&#xff0c;這里不做詳細介紹。而rma4go (redis memory analyzer for golang) 是一個redis的內存分析工具&#xff0c;這個工具的主要作用是針對運行時期的redis進行內存的分析&#xff0c;統計redis中key的分布情…

從Jupyter Notebook到腳本

16 Aug: My second article: From Scripts To Prediction API8月16日&#xff1a;我的第二篇文章&#xff1a; 從腳本到預測API As advanced beginners, we know quite a lot: EDA, ML concepts, model architectures etc…… We can write a big Jupyter Notebook, click “Re…

【EasyNetQ】- 使用Future Publish調度事件

許多業務流程要求在將來某個日期安排事件。例如&#xff0c;在與客戶進行初次銷售聯系后&#xff0c;我們可能希望在將來的某個時間安排跟進電話。EasyNetQ可以通過其Future Publish功能幫助您實現此功能。例如&#xff0c;這里我們使用FuturePublish擴展方法來安排未來一個月的…

Java這些多線程基礎知識你會嗎?

0、并發和并行、進程核線程、多進程和多線程的區別&#xff1a; &#xff08;這里的時間和時刻上的概念同物理上的一樣&#xff09; 并發&#xff1a;在一段時間內多個任務同時執行&#xff0c;或者說是在一段很短的時間內可以執行多條程序指令&#xff0c;微觀上看起來好像是可…

MySQL set names 命令_mysql set names 命令和 mysql 字符編碼問題

先看下面的執行結果&#xff1a;(rootlocalhost)[(none)]mysql>show variables like character%;---------------------------------------------------------------------------------------| Variable_name | Value |---------------------------------------------------…

設置Proxy Server和SQL Server實現數據庫安全

首先&#xff0c;我們需要了解一下SQL Server在WinSock上定義協議的步驟&#xff1a; 1. 在”啟動”菜單上&#xff0c;指向”程序/Microsoft Proxy Server”&#xff0c;然后點擊”Microsoft Management Console”。 2. 展開”Internet Information Service”,再展開運行Proxy…

Python django解決跨域請求的問題

解決方案 1.安裝django-cors-headers pip3 install django-cors-headers 2.配置settings.py文件 INSTALLED_APPS [...corsheaders&#xff0c;...] MIDDLEWARE_CLASSES (...corsheaders.middleware.CorsMiddleware,django.middleware.common.CommonMiddleware, # 注意順序...…

加勒比海兔_加勒比海海洋物種趨勢

加勒比海兔Ok, here’s a million dollar question: is the Caribbean really dying? Or, more specifically, are marine species found on Caribbean reefs becoming less abundant?好吧&#xff0c;這是一個百萬美元的問題&#xff1a;加勒比海真的死了嗎&#xff1f; 或者…