Description

老 C 是個程序員。
作為一個懶惰的程序員,老 C 經常在電腦上玩方塊游戲消磨時間。游戲被限定在一個由小方格排成的R行C列網格上
,如果兩個小方格有公共的邊,就稱它們是相鄰的,而且有些相鄰的小方格之間的公共邊比較特殊。特殊的公共邊排
列得有很強的規律。首先規定,第1行的前兩個小方格之間的邊是特殊邊。然后,特殊邊在水平方向上每4個小方格為
一個周期,在豎直方向上每2個小方格為一個周期。所有的奇數列與下一列之間都有特殊邊,且所在行的編號從左到
右奇偶交替。下圖所示是一個R = C = 8的網格,藍色標注的邊是特殊邊。首先,在第1行,第1列和第2列之間有一條
特殊邊。因為豎直方向周期為2,所以所有的奇數行,第1列和第2列之間都有特殊邊。因為水平方向周期為4,所以所
有奇數行的第5列和第6列之間也有特殊邊,如果網格足夠大,所有奇數行的第9列和第10列、第13列和第14列之間都
有特殊邊。因為所有的奇數列和下一列之間都有特殊邊,所以第3列和第4列、第7列和第8列之間也有特殊邊,而所在
行的編號從左到右奇偶交替,所以它們的特殊邊在偶數行。如果網格的規模更大,我們可以用同樣的方法找出所有的
特殊邊。

網格的每個小方格剛好可以放入一個小方塊,在游戲的一開始,有些小方格已經放上了小方塊,另外的小方格沒有放
。老 C 很討厭下圖所示的圖形,如果他發現有一些小方塊排列成了它討厭的形狀(特殊邊的位置也要如圖中所示),
就很容易棄療,即使是經過任意次旋轉、翻轉后排列成討厭的形狀,老 C 也同樣容易棄療。

為了防止棄療,老 C 決定趁自己還沒有棄療,趕緊移除一些格子里小方塊,使得剩下的小方塊不能構成它討厭的形狀
。但是游戲里每移除一個方塊都是要花費一些金幣的,每個方塊需要花費的金幣有多有少參差不齊。老 C 當然希望
盡可能少的使用游戲里的金幣,但是最少要花費多少金幣呢?老 C 懶得思考,就把這個問題交給你了

Input

第一行有3個正整數C, R, n,表示C列R行的網格中,有n個小方格放了小方塊。
接下來n行,每行3個正整數x, y, w,表示在第x列第y行的小方格里放了小方塊,移除它需要花費w個金幣。保證不會
重復,且都在網格范圍內。
1 ≤ C, R, n ≤ 10^5 , 1 ≤ w ≤ 10^4

Output

輸出一行,包含一個整數,表示最少花費的金幣數量。

Sample Input

2 2 4

1 1 5

1 2 6

2 1 7

2 2 8

Sample Output

5

---

簡要題解

染色分層+最小割

---

想法

觀察使老C棄療的圖形

發現它們都由特殊邊兩邊的紫色格子，及一個藍格子、一個綠格子組成。

由此我們可以給整張圖染色

（為了方便我把兩個紫格子分別染成紫與深藍）

我們需要移除一些格子使圖中不存在連續的 藍-紫-深藍-綠 或 綠-紫-深藍-藍
由此可以想到用最小割（有一句話說得好：靈感源于性質的相似性）
最小割即把對點的限制轉換到對邊的限制上。

開始建圖。
S向每個綠格子連邊，容量為綠格子的w
每個綠格子向相鄰的紫格子與深藍格子連邊，容量為INF
紫格子與相鄰深藍格子互相連邊，容量為兩個格子w的min （其實這兩個相鄰的點是一體的，就相當于是一個大點。這兩個點中間連邊相當于拆大點。）
紫格子與深藍格子向相鄰的藍格子連邊，容量為INF
藍格子向T連邊，容量為藍格子的w

---

代碼

這道題A的真是不容易……
一開始懶得寫hash表光寫個hash，結果那么不幸就被卡上了……
（哎，這是第二次了……之前有一次cf沒寫hash表被hack了…）
調了好久好久，不開森。

#include<cstdio> #include<iostream> #include<algorithm> #include<vector>#define INF 2000000007 #define P 100999using namespace std;typedef long long ll; const int N = 100007;struct node{int v,f;node *next,*rev; }pool[N*10],*h[N]; int cnt;void addedge(int u,int v,int f){node *p=&pool[++cnt],*q=&pool[++cnt];p->v=v;p->next=h[u];h[u]=p; p->f=f;p->rev=q;q->v=u;q->next=h[v];h[v]=q; q->f=0;q->rev=p; }int S,T; int que[N],level[N]; bool bfs(){int head=0,tail=0,u,v;for(int i=S;i<=T;i++) level[i]=-1;level[S]=1; que[tail++]=S;while(head<tail){u=que[head++];for(node *p=h[u];p;p=p->next)if(p->f && level[v=p->v]==-1){level[v]=level[u]+1;que[tail++]=v; }if(level[T]!=-1) return true;} return false; } int find(int u,int f){int v,s=0,t;if(u==T) return f;for(node *p=h[u];p;p=p->next)if(p->f && s<f && level[v=p->v]==level[u]+1){t=find(v,min(p->f,f-s));if(t){s+=t;p->f-=t;p->rev->f+=t;}}if(!s) level[u]=-1;return s; } int dinic(){int flow=0;while(bfs()) flow+=find(S,INF);return flow; }int C,R,n;struct data{int x,y,w,id; }d[N];int hash(int x,int y) { if(x<=0 || y<=0 || x>R || y>C) return P;return ((ll)x*N+y)%P; } vector<data> hh[P+1];int check(int c,int x,int y){if(c==P) return 0;for(int i=0;i<hh[c].size();i++)if(hh[c][i].x==x && hh[c][i].y==y) return hh[c][i].id;return 0; }int main() {scanf("%d%d%d",&C,&R,&n);for(int i=1;i<=n;i++){scanf("%d%d%d",&d[i].y,&d[i].x,&d[i].w);d[i].id=i;hh[hash(d[i].x,d[i].y)].push_back(d[i]);}//addedgeint t,xx,yy;S=0; T=n+1;for(int i=1;i<=n;i++){xx=d[i].x%2; yy=d[i].y%4;if((xx==1 && yy==1) || (xx==0 && yy==3)){ //purplet=check(hash(d[i].x,d[i].y+1),d[i].x,d[i].y+1);if(t) addedge(i,t,min(d[i].w,d[t].w));}else if((xx==1 && yy==2) || (xx==0 && yy==0)){ //dark bluet=check(hash(d[i].x,d[i].y-1),d[i].x,d[i].y-1);if(t) addedge(i,t,min(d[i].w,d[t].w)); }else if((xx==1 && yy==3) || (xx==0 && yy==2)){ //greenaddedge(S,i,d[i].w);t=check(hash(d[i].x+1,d[i].y),d[i].x+1,d[i].y);if(t) addedge(i,t,INF);t=check(hash(d[i].x-1,d[i].y),d[i].x-1,d[i].y);if(t) addedge(i,t,INF);if(yy==3) t=check(hash(d[i].x,d[i].y-1),d[i].x,d[i].y-1);else t=check(hash(d[i].x,d[i].y+1),d[i].x,d[i].y+1);if(t) addedge(i,t,INF); }else{ //blueaddedge(i,T,d[i].w);t=check(hash(d[i].x+1,d[i].y),d[i].x+1,d[i].y);if(t) addedge(t,i,INF);t=check(hash(d[i].x-1,d[i].y),d[i].x-1,d[i].y);if(t) addedge(t,i,INF);if(yy==1) t=check(hash(d[i].x,d[i].y-1),d[i].x,d[i].y-1);else t=check(hash(d[i].x,d[i].y+1),d[i].x,d[i].y+1);if(t) addedge(t,i,INF); }}printf("%d\n",dinic());return 0; }

轉載于:https://www.cnblogs.com/lindalee/p/8447250.html

總結

以上是生活随笔為你收集整理的[bzoj4823][洛谷P3756][Cqoi2017]老C的方块的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。