点阵

C++(g++ 7.5.0) 解法, 执行用时: 18ms, 内存消耗: 1176K, 提交时间: 2023-04-21 15:20:59

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int max_n = 20000;
const int max_m = 500000;
const int inf = 2e9;
int n, m;
struct edge{
    int to, cap, rev, next;
}E[max_m];
int head[max_n];
int cnt = 1;
void add(int from, int to, int cap) {
    E[cnt].to = to;
    E[cnt].cap = cap;
    E[cnt].rev = cnt + 1;
    E[cnt].next = head[from];
    head[from] = cnt++;
    E[cnt].to = from;
    E[cnt].cap = 0;
    E[cnt].rev = cnt - 1;
    E[cnt].next = head[to];
    head[to] = cnt++;
}

int iter[max_n];
int dist[max_n];
bool searchpath(int s,int t) {
    fill(dist, dist + t + 10, -1);
    queue<int> que;que.push(s);
    dist[s] = 0;
    while (!que.empty()) {
        int u = que.front();que.pop();
        for (int i = head[u];i;i = E[i].next) {
            edge& e = E[i];
            if (dist[e.to] != -1 || e.cap == 0)continue;
            dist[e.to] = dist[u] + 1;
            que.push(e.to);
        }
    }return dist[t] != -1;
}
int matchpath(int u, int t, int f) {
    if (u == t)return f;
    for (int& i = iter[u];i;i = E[i].next) {
        edge& e = E[i];
        if (dist[e.to] <= dist[u] || e.cap == 0)continue;
        int d = matchpath(e.to, t, min(e.cap, f));
        if (d > 0) {
            e.cap -= d;
            E[e.rev].cap += d;
            return d;
        }
    }return false;
}
int dinic(int start,int ed) {
    int flow = 0;int f;
    while (searchpath(start, ed)) {
        for (int i = 1;i <= ed;++i)iter[i] = head[i];
        while (f = matchpath(start, ed, inf))
            flow += f;
    }return flow;
}

int getpoint(int x,int y) {
    return (x - 1) * (n - 1) + y;
}
bool check(int x,int y) {
    return x > 0 && x <= n - 1 && y > 0 && y <= n - 1;
}
int dirx[4] = { 1,-1,0,0 };
int diry[4] = { 0,0,1,-1 };
char mp[200][200];
int main() {
    ios::sync_with_stdio(0);
    cin >> n;
    for (int i = 1;i <= 2 * n - 1;++i)
        for (int j = 1;j <= 2 * n - 1;++j)
            cin >> mp[i][j];
    int start = (n - 1) * (n - 1) + 1;
    int ed = start + 1;
    for (int i = 1;i <= (n - 1);++i) {
        for (int j = 1;j <= (n - 1);++j) {
            int colour = ((i + j) & 1);
            int cuut = 0;
            int x = i * 2;int y = j * 2;
            for (int k = 0;k < 4;k++) {
                int xk = x + dirx[k];
                int yk = y + diry[k];
                if (mp[xk][yk] != '.')continue;
                ++cuut;
                if (colour == 0) {
                    if (check(i + dirx[k], j + diry[k]))
                        add(getpoint(i, j), getpoint(i + dirx[k], j + diry[k]), 1);
                    else add(getpoint(i, j), ed, 1);
                }
                else if (!check(i + dirx[k], j + diry[k]))
                    add(start, getpoint(i, j), 1);
            }if (colour == 0)
                add(start, getpoint(i, j), cuut - 1);
            else add(getpoint(i, j), ed, cuut - 1);
        }
    }cout << dinic(start, ed) + 1 << endl;
}

C++14(g++5.4) 解法, 执行用时: 16ms, 内存消耗: 1244K, 提交时间: 2020-08-30 10:29:58

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int max_n = 20000;
const int max_m = 500000;
const int inf = 2e9;
int n, m;
struct edge{
	int to, cap, rev, next;
}E[max_m];
int head[max_n];
int cnt = 1;
void add(int from, int to, int cap) {
	E[cnt].to = to;
	E[cnt].cap = cap;
	E[cnt].rev = cnt + 1;
	E[cnt].next = head[from];
	head[from] = cnt++;
	E[cnt].to = from;
	E[cnt].cap = 0;
	E[cnt].rev = cnt - 1;
	E[cnt].next = head[to];
	head[to] = cnt++;
}

int iter[max_n];
int dist[max_n];
bool searchpath(int s,int t) {
	fill(dist, dist + t + 10, -1);
	queue<int> que;que.push(s);
	dist[s] = 0;
	while (!que.empty()) {
		int u = que.front();que.pop();
		for (int i = head[u];i;i = E[i].next) {
			edge& e = E[i];
			if (dist[e.to] != -1 || e.cap == 0)continue;
			dist[e.to] = dist[u] + 1;
			que.push(e.to);
		}
	}return dist[t] != -1;
}
int matchpath(int u, int t, int f) {
	if (u == t)return f;
	for (int& i = iter[u];i;i = E[i].next) {
		edge& e = E[i];
		if (dist[e.to] <= dist[u] || e.cap == 0)continue;
		int d = matchpath(e.to, t, min(e.cap, f));
		if (d > 0) {
			e.cap -= d;
			E[e.rev].cap += d;
			return d;
		}
	}return false;
}
int dinic(int start,int ed) {
	int flow = 0;int f;
	while (searchpath(start, ed)) {
		for (int i = 1;i <= ed;++i)iter[i] = head[i];
		while (f = matchpath(start, ed, inf))
			flow += f;
	}return flow;
}

int getpoint(int x,int y) {
	return (x - 1) * (n - 1) + y;
}
bool check(int x,int y) {
	return x > 0 && x <= n - 1 && y > 0 && y <= n - 1;
}
int dirx[4] = { 1,-1,0,0 };
int diry[4] = { 0,0,1,-1 };
char mp[200][200];
int main() {
	ios::sync_with_stdio(0);
	cin >> n;
	for (int i = 1;i <= 2 * n - 1;++i)
		for (int j = 1;j <= 2 * n - 1;++j)
			cin >> mp[i][j];
	int start = (n - 1) * (n - 1) + 1;
	int ed = start + 1;
	for (int i = 1;i <= (n - 1);++i) {
		for (int j = 1;j <= (n - 1);++j) {
			int colour = ((i + j) & 1);
			int cuut = 0;
			int x = i * 2;int y = j * 2;
			for (int k = 0;k < 4;k++) {
				int xk = x + dirx[k];
				int yk = y + diry[k];
				if (mp[xk][yk] != '.')continue;
				++cuut;
				if (colour == 0) {
					if (check(i + dirx[k], j + diry[k]))
						add(getpoint(i, j), getpoint(i + dirx[k], j + diry[k]), 1);
					else add(getpoint(i, j), ed, 1);
				}
				else if (!check(i + dirx[k], j + diry[k]))
					add(start, getpoint(i, j), 1);
			}if (colour == 0)
				add(start, getpoint(i, j), cuut - 1);
			else add(getpoint(i, j), ed, cuut - 1);
		}
	}cout << dinic(start, ed) + 1 << endl;
}

C++ 解法, 执行用时: 14ms, 内存消耗: 1036K, 提交时间: 2022-05-06 21:42:56

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10,M=1e5+10,INF=1e8;
int ne[M],e[M],h[N],idx;
char mp[210][210];
int f[M];
int dx[4]={0,-1,0,1},dy[4]={1,0,-1,0};
int d[N],cur[N],q[N];
int S,T;
int n;
void add(int a,int b,int c)
{
	ne[idx]=h[a],e[idx]=b,f[idx]=c,h[a]=idx++;
	ne[idx]=h[b],e[idx]=a,f[idx]=0,h[b]=idx++;
}
bool check(int x,int y)
{
	return x>0&&x<=n-1&&y>0&&y<=n-1;
}
int get(int x,int y)
{
	return (x-1)*(n-1)+y;
}
bool bfs()
{
	memset(d,-1,sizeof d);
	int hh=0,tt=0;
    d[S]=0,q[0]=S;
    cur[S] = h[S];
    while(hh<=tt)
    {
    	int t=q[hh++];
    	for(int i=h[t];~i;i=ne[i])
    	{
    		int j=e[i];
    		if(f[i]&&d[j]==-1)
    		{    
    		    d[j]=d[t]+1;
    			 cur[j]=h[j];
    			if(j==T)return true;
                 q[++tt]=j;
    		}
    	}
    }
    return false;
}
int find(int u,int limit)
{
	if(T==u)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;
	int flow;
	while(bfs())while(flow=find(S,INF))r+=flow;
	return r;
}
int main()
{	
   memset(h,-1,sizeof h);
   cin>>n;
   for(int i=1;i<=2*n-1;i++)
   	for(int j=1;j<=2*n-1;j++)
   	    cin>>mp[i][j];
   	 S=(n-1)*(n-1)+1;
   	 T=S+1;
   	for(int i=1;i<=n-1;i++)
   	 for(int j=1;j<=n-1;j++)
   	 {
   	 	int color=((i+j)&1);
   	 	int cnt=0;
   	 	int x=i*2,y=j*2;
   	 	for(int k=0;k<4;k++)
   	 	{
   	 		int nx=dx[k]+x,ny=dy[k]+y;
   	 		if(mp[nx][ny]!='.')continue;
   	 		cnt++;
   	 		if(color==0)
   	 		{
   	 			if(check(i+dx[k],j+dy[k]))
   	 				add(get(i,j),get(i+dx[k],j+dy[k]),1);
   	 			else add(get(i,j),T,1);
   	 		}
   	   	else if(!check(i+dx[k],j+dy[k]))add(S,get(i,j),1);
   	 	}
   	 	 if(color==0)add(S,get(i,j),cnt-1);
   	 	 else add(get(i,j),T,cnt-1);
   	 }
   	 cout<<dinic()+1<<endl;
   	 return 0;
}

详情