[网络流24题]骑士共存问题

C++(clang++ 11.0.1) 解法, 执行用时: 91ms, 内存消耗: 5652K, 提交时间: 2022-09-07 21:33:41

#include<bits/stdc++.h>
using namespace std ;

const int N = 40005, M = 1e6 + 5, INF = 2147483647 ;
struct Edge
{
    int nxt,to,c ;
}e[M] ;
int head[N],now[N],d[N],tot=1 ;
int S,T ;
queue<int>q ;
void add(int from,int to,int c)
{
    e[++tot].to=to ; e[tot].c=c ; e[tot].nxt=head[from] ; head[from]=tot ;
    e[++tot].to=from ; e[tot].c=0 ; e[tot].nxt=head[to] ; head[to]=tot ;
}
bool bfs()
{
    memset(d,0,sizeof(d)) ;
    while(!q.empty()) q.pop() ;
    q.push(S) ; d[S]=1 ; now[S]=head[S] ;
    while(!q.empty())
    {
        int x=q.front() ; q.pop() ;
        for(int i=head[x];i;i=e[i].nxt)
        {
            int y=e[i].to ;
            if(e[i].c&&!d[y])
            {
                q.push(y) ;
                now[y]=head[y] ;
                d[y]=d[x]+1 ;
                if(y==T) return 1 ;
            }
        }
    }
    return 0 ;
}
int dinic(int x,int flow)
{
    if(x==T) return flow ;
    int rest=flow,k ;
    for(int i=now[x];i&&rest;i=e[i].nxt)
    {
        int y=e[i].to ;
        now[x]=i ;
        if(e[i].c&&d[y]==d[x]+1)
        {
            k=dinic(y,min(e[i].c,rest)) ;
            if(!k) d[y]=0 ;
            e[i].c-=k ;
            e[i^1].c+=k ;
            rest-=k ;
        }
    }
    return flow-rest ;
}
//主函数
int n,m ;
bool a[N][N] ;
int dx[8]={-1,-2,-2,-1,1,2,2,1},
    dy[8]={-2,-1,1,2,-2,-1,1,2};
bool check(int x,int y)
{
    return x>0&&y>0&&x<=n&&y<=n ;
}
int get(int x,int y)
{
    return (x-1)*n+y ;
}
int main()
{
    cin>>n>>m ;
    for(int i=1,x,y;i<=m;++i)
    {
        cin>>x>>y ;
        a[x][y]=1 ;
    }
    S=n*n+1 ; T=S+1 ;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;j++) if((i+j)&1)
        {
            if(a[i][j]) continue ;
            add(S,get(i,j),1) ;
            for(int k=0;k<8;++k)
            {
                int x=i+dx[k],y=j+dy[k] ;
                if(check(x,y)&&!a[x][y]) add(get(i,j),get(x,y),1) ;
            }
        }
        else if(!a[i][j]) add(get(i,j),T,1) ;
    int flow,maxflow=0 ;
    while(bfs())
        while(flow=dinic(S,INF)) maxflow+=flow ;
    cout<<n*n-m-maxflow<<'\n' ;
    return 0 ;
}

C++(g++ 7.5.0) 解法, 执行用时: 211ms, 内存消耗: 5640K, 提交时间: 2023-01-03 15:24:59

// 最大独立集

#include<bits/stdc++.h>
using namespace std;
const int N = 40010, M = 500010, INF = 1e8;
int h[N], e[M], ne[M], f[M], idx, d[N], n, m, S, T, cur[M];

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, INF)) r += flow;
    return r;
}
int get(int x, int y)
{
	return (x - 1) * n + y;
}
char g[210][210];
int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2}, dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
int main()
{
    memset(h, -1, sizeof h);
	
	cin >> n >> m;

	S = 0, T = n * n + 1;	

	for(int i = 1; i <= m; i ++ )
	{
		int x, y;
		cin >> x >> y;
		g[x][y] = 'X';
	}
    int res = n * n - m;
	for(int i = 1; i <= n; i ++ )
		for(int j = 1; j <= n; j ++ )
			if((i + j & 1) && g[i][j] != 'X')
			{
				add(S, get(i, j), 1);
				for(int k = 0; k < 8; k ++ )
				{
					int a = i + dx[k], b = j + dy[k];
					if(a < 1 || b < 1 || a > n || b > n || g[a][b] == 'X') continue;
					add(get(i, j), get(a, b), INF);
				}
			}
			else if(g[i][j] != 'X')
				add(get(i, j), T, 1);
	cout << res - dinic() << '\n';
}

详情