[CQOI2017]老C的方块

C++(g++ 7.5.0) 解法, 执行用时: 309ms, 内存消耗: 17752K, 提交时间: 2022-12-30 11:24:51

#include<bits/stdc++.h>
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
const int N = 5e5 + 10, M = 5e5 + 10, INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int, int>PII;
int h[N], e[M], ne[M], f[M], idx, d[N], n, m, S, T, cur[M], t, x[N], y[N];

void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], f[idx] = c, h[a] = idx ++;
    e[idx] = a, ne[idx] = h[b], f[idx] = 0, h[b] = idx ++; 
}

bool bfs()
{
    queue<int>q;
    memset(d, -1, sizeof d);
    q.push(S);
    d[S] = 0;
    cur[S] = h[S];
    while(!q.empty())
    {
        auto t = q.front();
        q.pop();
        
        for(int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if((d[j] == -1) && f[i])
            {
                d[j] = d[t] + 1;
                cur[j] = h[j];
                if(j == T) return true;
                q.push(j);
            }
        }
    }
    return false;
}

int find(int u, int limit)
{
    if(u == T) return limit;
    int flow = 0;
    for(int i = cur[u]; ~i && flow < limit; i = ne[i])
    {
        int j = e[i];
        cur[u] = i;
        if((d[j] == d[u] + 1) && f[i])
        {
            int t = find(j, min(f[i], limit - flow));
            if(!t) d[j] = -1;
            f[i] -= t, f[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}

int dinic()
{
    int r = 0, flow;
    while(bfs()) while(flow = find(S, 0x3f3f3f3f)) r += flow;
	return r;    
}
map<PII, int>mp;
// int get(int x, int y)
// {
// 	if(x % 4 == 1) return ((y & 1) ? 2 : 1);
// 	if(x % 4 == 2) return ((y & 1) ? 3 : 4);
// 	if(x % 4 == 3) return ((y & 1) ? 1 : 2);
// 	return ((y & 1) ? 4 : 3);
// }
int get(int x, int y) {
if (x % 4 == 1) return (y & 1) ? 2 : 1;
if (x % 4 == 2) return (y & 1) ? 3 : 4;
if (x % 4 == 3) return (y & 1) ? 4 : 3;
if (x % 4 == 0) return (y & 1) ? 1 : 2;
return 0;
}

int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};


void solve()
{
	cin >> n >> m >> t;
	memset(h, -1, sizeof h);
	S = N - 1, T = S - 1;
	for(int i = 1; i <= t; i ++ )
	{
		int w;
		cin >> x[i] >> y[i] >> w;
		mp[{x[i], y[i]}] = i;
		add(i, i + t, w); // 拆点
	}

	for(int i = 1; i <= t; i ++ )
	{
		int t1 = get(x[i], y[i]);
		if(t1 == 1) add(S, i, INF);
		if(t1 == 4) add(i + t, T, INF);
		for(int d = 0; d < 4; d ++ )
		{
			int a = x[i] + dx[d], b = y[i] + dy[d];
			if(!mp.count({a, b})) continue;
			int j = mp[{a, b}], t2 = get(a, b);
			if(t1 == 1 && t2 == 2) add(i + t, j, INF);
			if(t1 == 2 && t2 == 3) add(i + t, j, INF);
			if(t1 == 3 && t2 == 4) add(i + t, j, INF);
		}
	}

	cout << dinic() << '\n';
}
signed main()
{
	io;
	int T = 1;
	//cin >> T;
	while(T -- )
	solve();
}

C++(clang++11) 解法, 执行用时: 148ms, 内存消耗: 20984K, 提交时间: 2021-02-14 12:59:36

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<map>
using namespace std;
int gi(){
    int x=0,w=1;char ch=getchar();
    while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if (ch=='-') w=0,ch=getchar();
    while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return w?x:-x;
}
const int N = 1e5+5;
const int inf = 2e9;
struct edge{int to,nxt,w;}a[N<<4];
int n,x[N],y[N],val[N],col[N],S,T,head[N],cnt=1,dep[N],cur[N];
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
map<int,int>M[N];queue<int>Q;
void link(int u,int v,int w){
    a[++cnt]=(edge){v,head[u],w};head[u]=cnt;
    a[++cnt]=(edge){u,head[v],0};head[v]=cnt;
}
bool bfs(){
    memset(dep,0,sizeof(dep));
    dep[S]=1;Q.push(S);
    while (!Q.empty()){
        int u=Q.front();Q.pop();
        for (int e=head[u];e;e=a[e].nxt)
            if (a[e].w&&!dep[a[e].to])
                dep[a[e].to]=dep[u]+1,Q.push(a[e].to);
    }
    return dep[T];
}
int dfs(int u,int f){
    if (u==T) return f;
    for (int &e=cur[u];e;e=a[e].nxt)
        if (a[e].w&&dep[a[e].to]==dep[u]+1){
            int tmp=dfs(a[e].to,min(a[e].w,f));
            if (tmp) {a[e].w-=tmp;a[e^1].w+=tmp;return tmp;}
        }
    return 0;
}
int dinic(){
    int res=0;
    while (bfs()){
        for (int i=1;i<=T;++i) cur[i]=head[i];
        while (int tmp=dfs(S,inf)) res+=tmp;
    }
    return res;
}
void build1(int v){
    for (int d=0;d<4;++d){
        int i=x[v]+dx[d],j=y[v]+dy[d],u=M[i][j];
        if (u)
            if (col[u]==2) link(v,u,min(val[u],val[v]));
            else link(u,v,inf);
    }
}
void build2(int u){
    for (int d=0;d<4;++d){
        int i=x[u]+dx[d],j=y[u]+dy[d],v=M[i][j];
        if (v)
            if (col[v]==1) link(u,v,min(val[u],val[v]));
            else link(u,v,inf);
    }
}
int main(){
    gi();gi();n=gi();S=n+1;T=S+1;
    for (int i=1;i<=n;++i){
        x[i]=gi(),y[i]=gi(),val[i]=gi();
        M[x[i]][y[i]]=i;
        col[i]=(x[i]%4>=2)*2+(((x[i]+y[i])&1)^1);
    }
    for (int i=1,j;i<=n;++i)
        if (col[i]==0) link(S,i,val[i]);
        else if (col[i]==1) build1(i);
        else if (col[i]==2) build2(i);
        else link(i,T,val[i]);
    printf("%d\n",dinic());return 0;
}

详情