P3756老C的方块题解
Stuart220_Chen · · 题解
我个人的第一道黑题。
首先看到这道题奇奇怪怪的限制条件，那肯定是网络流没跑了。至于求最小值并且是删边的话，那就锁定为最小割。
而这题又是网格图，所以不妨考虑网格染色。
我们会发现，它的每一种图都是在关键边左右各放置一个
我们会发现每个
然后按照黄黑绿红的顺序连边，这里边只要有一个没有，就可以破坏掉这个块，其中，原点连向黄格子，红格子连向汇点，黑点绿点分成入点和出点来做。
注意事项：
含第一、二个格子之间的关键边的块和含第三、四个格子之间的关键边的块连边顺序不一样，需要分类讨论。
上代码：
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define int long long
struct IO
{
static const int Size=(1<<21);
char buf[Size],*p1,*p2;
int st[105],Top;
~IO(){clear();}
il void clear(){fwrite(buf,1,Top,stdout);Top=0;}
il char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,Size,stdin),p1==p2)?EOF:*p1++;}
il void pc(const char c){Top==Size&&(clear(),0);buf[Top++]=c;}
il IO& operator >>(char& c){while(c=gc(),c==' ' || c=='\n' || c=='\r');return *this;}
template<typename T>il IO& operator >>(T& x)
{
x=0;bool f=0;char c=gc();
while(!isdigit(c)){if(c=='-') f=1;c=gc();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();}
f?x=-x:0;
return *this;
}
il IO& operator >>(string& s)
{
s="";char c=gc();
while(c==' ' || c=='\n' || c=='\r') c=gc();
while(c!=' ' && c!='\n' && c!='\r' && c!=EOF) s+=c,c=gc();
return *this;
}
il IO& operator <<(const char c){pc(c);return *this;}
template<typename T> il IO& operator <<(T x)
{
if(x<0) pc('-'),x=-x;
do st[++st[0]]=x%10,x/=10;while(x);
while(st[0]) pc(st[st[0]--]+'0');
return *this;
}
il IO& operator <<(const string s){for(auto c:s) pc(c);return *this;}
il IO& operator <<(const char* c){for(int i=0;c[i];i++) pc(c[i]);return *this;}
} fin,fout;//快读
const int N=100010,inf=1e18;
int C,R,n,h[N<<1],cur[N<<1],tot=1,cnt,dis[N<<1],S,T,c[N],ansf;
map<int,int> mp[N];
queue<int> q;
struct edge
{
int v,next,w;
} e[N<<3];
void add(int u,int v,int w)
{
e[++tot].next=h[u];
e[tot].v=v;e[tot].w=w;
h[u]=tot;
}
void add_edge(int u,int v,int w)
{
add(u,v,w);add(v,u,0);
}
bool bfs()
{
for(int i=1;i<=cnt;i++) cur[i]=h[i],dis[i]=0;
dis[S]=1,q.push(S);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=h[u];i;i=e[i].next)
{
int v=e[i].v;
if(e[i].w && !dis[v])
{
dis[v]=dis[u]+1;
q.push(v);
}
}
}
return dis[T];
}
int dfs(int u,int val)
{
if(u==T) return val;
int w=0;
for(int& i=cur[u];i;i=e[i].next)
{
int v=e[i].v;
if(e[i].w && dis[v]==dis[u]+1)
{
int x=dfs(v,min(e[i].w,val-w));
if(x>0) w+=x,e[i].w-=x,e[i^1].w+=x;
if(w==val) return w;
}
}
return w;
}
void dinic()
{
while(bfs()) ansf+=dfs(S,inf);
}//模板Dinic
signed main()
{
fin>>C>>R>>n;
for(int i=1;i<=n;i++)
{
int x,y;
fin>>x>>y>>c[i];
mp[y][x]=i;
}
cnt=n*2+2;S=cnt-1,T=cnt;
for(int i=1;i<=R;i++)
{
for(auto x:mp[i])
{
int j=x.first;
if(j%4==1 && i%2==1)
{
add_edge(x.second,x.second+n,c[x.second]);
if(mp[i].find(j+1)!=mp[i].end()) add_edge(x.second+n,mp[i][j+1],inf);
}
if(j%4==2 && i%2==1)
{
add_edge(x.second,x.second+n,c[x.second]);
if(mp[i].find(j-1)!=mp[i].end()) add_edge(mp[i][j-1]+n,x.second,inf);
}
if(j%4==3 && i%2==0)
{
add_edge(x.second,x.second+n,c[x.second]);
if(mp[i].find(j+1)!=mp[i].end()) add_edge(mp[i][j+1]+n,x.second,inf);
}
if(j%4==0 && i%2==0)
{
add_edge(x.second,x.second+n,c[x.second]);
if(mp[i].find(j-1)!=mp[i].end()) add_edge(x.second+n,mp[i][j-1],inf);
}
if(j%4==1 && i%2==0)
{
add_edge(S,x.second,c[x.second]);
if(mp[i-1].find(j)!=mp[i-1].end()) add_edge(x.second,mp[i-1][j],inf);
if(mp[i+1].find(j)!=mp[i+1].end()) add_edge(x.second,mp[i+1][j],inf);
if(mp[i].find(j-1)!=mp[i].end()) add_edge(x.second,mp[i][j-1],inf);
}
if(j%4==0 && i%2==1)
{
add_edge(S,x.second,c[x.second]);
if(mp[i-1].find(j)!=mp[i-1].end()) add_edge(x.second,mp[i-1][j],inf);
if(mp[i+1].find(j)!=mp[i+1].end()) add_edge(x.second,mp[i+1][j],inf);
if(mp[i].find(j+1)!=mp[i].end()) add_edge(x.second,mp[i][j+1],inf);
}
if(j%4==3 && i%2==1)
{
add_edge(x.second,T,c[x.second]);
if(mp[i-1].find(j)!=mp[i-1].end()) add_edge(mp[i-1][j]+n,x.second,inf);
if(mp[i+1].find(j)!=mp[i+1].end()) add_edge(mp[i+1][j]+n,x.second,inf);
if(mp[i].find(j-1)!=mp[i].end()) add_edge(mp[i][j-1]+n,x.second,inf);
}
if(j%4==2 && i%2==0)
{
add_edge(x.second,T,c[x.second]);
if(mp[i-1].find(j)!=mp[i-1].end()) add_edge(mp[i-1][j]+n,x.second,inf);
if(mp[i+1].find(j)!=mp[i+1].end()) add_edge(mp[i+1][j]+n,x.second,inf);
if(mp[i].find(j+1)!=mp[i].end()) add_edge(mp[i][j+1]+n,x.second,inf);
}
}
}
//恶心的分讨建图，我恨分讨
dinic();
fout<<ansf;
return 0;
}至于这题复杂度的话，一共