Magic Slab

C++(g++ 7.5.0) 解法, 执行用时: 5ms, 内存消耗: 1028K, 提交时间: 2022-08-28 17:36:21

#include<bits/stdc++.h>
using namespace std ;
const int N = 1e5 + 5, M = 7e5 + 5, INF = 2147483647 ;
struct Edge
{
    int nxt,to,c ;
}e[M] ;
int head[N],now[N],d[N],tot=1 ;
int n,m,S,T ;
queue<int>q ;
void add(int from,int to,int c)
{
    //printf("%d %d %d\n",from,to,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 main()
{
    scanf("%d%d",&n,&m) ;
    S=(n+1)*(n+1) ; T=S+1 ; 
    int val=0 ;
    for(int i=1;i<=n;++i)
        for(int j=1,x;j<=n;j++)
        {
            scanf("%d",&x) ;
            add((i-1)*n+j,T,x) ;
            add(i+n*n,(i-1)*n+j,INF) ;
            add(j+n+n*n,(i-1)*n+j,INF) ;
            val+=x ;
        }
    for(int i=1,x;i<=n;++i) 
    {
        scanf("%d",&x) ;
        add(S,i+n*n,x) ;
    }
    for(int i=1,x;i<=n;++i)
    {
        scanf("%d",&x) ;
        add(S,i+n+n*n,x) ;
    }
    for(int i=1,a,b,c,d,e;i<=m;++i)
    {
        scanf("%d%d%d%d%d",&a,&b,&c,&d,&e) ;
        add(T+i,T,e) ; val+=e ;
        add(a+n*n,T+i,INF) ;
        add(c+n*n,T+i,INF) ;
        add(b+n+n*n,T+i,INF) ;
        add(d+n+n*n,T+i,INF) ;
    }
    int flow,maxflow=0 ;
    while(bfs()) 
        while(flow=dinic(S,INF)) maxflow+=flow ;
    printf("%d\n",val-maxflow) ;
    return 0 ;
}

C++14(g++5.4) 解法, 执行用时: 36ms, 内存消耗: 736K, 提交时间: 2019-05-04 11:57:14

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define inf 0x3f3f3f3f
#define ll long long
#define sscc ios::sync_with_stdio(false);
#define ms(a) memset(a,0,sizeof(a))
#define mss(a) memset(a,-1,sizeof(a))
#define msi(a) memset(a,inf,sizeof(a))
using namespace std;

const int M=45*45+45*2+10005;
const int N=45*45+45*2+10005;
const int mas=1e8+7;

struct A{
	int y,len,next;
}a[M*2];
int pre[N],cent=0;
int ce[N];
int q[N];
int be,en;

void add(int x,int y,int z)//前向星 
{
	a[cent].y=y,a[cent].len=z,a[cent].next=pre[x];
	pre[x]=cent++;
	a[cent].y=x,a[cent].len=0,a[cent].next=pre[y];
	pre[y]=cent++;
}

bool bfs()
{
	ms(ce);
	ce[be]=1;
	int l=0,r=1;
	q[r]=be;
	while(l<r)
	{
		int u=q[++l];
		for(int i=pre[u];~i;i=a[i].next)
		{
			int v=a[i].y;
			if(!ce[v]&&a[i].len)
				ce[v]=ce[u]+1,q[++r]=v;
		}
	}
	return ce[en]; 
}

int dfs(int u,int mi)
{
	int ans=0;
	if(mi==0||u==en)	return mi;
	for(int i=pre[u];~i;i=a[i].next) 
	{
		int v=a[i].y;
		if(ce[u]+1==ce[v]&&a[i].len)
		{
			int minn=dfs(v,min(mi-ans,a[i].len));
			a[i].len-=minn;
			a[i^1].len+=minn;
			ans+=minn; 
			if(ans==mi) 
				return ans;
		}
	}
	return ans;
}

int dinic(int x,int y)
{
	be=x,en=y;//起点、终点 
	int ans=0;
	while(bfs()) 
	{
		ans+=dfs(be,inf);//累加 
	}
	return ans;
}


int main()
{
	int t,n,m;
	int sum=0;
	mss(pre);
	cent=0;
	scanf("%d%d",&n,&m);//点数量、边数量 
	int T=n*n+2*n+m+1;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			int z;
			scanf("%d",&z);
			add(0,i*n+j+1,z);
			add(i*n+j+1,n*n+i+1,mas);
			add(i*n+j+1,n*n+n+j+1,mas);
			sum+=z;
		}
	}
	for(int i=1;i<=n;i++){
		int z;
		scanf("%d",&z);
		add(n*n+i,T,z);
	}
	for(int i=1;i<=n;i++){
		int z;
		scanf("%d",&z);
		add(n*n+n+i,T,z);
	}
	for(int i=1;i<=m;i++){
		int x,y,a1,b1,z;
		scanf("%d%d%d%d%d",&x,&y,&a1,&b1,&z);
		add(n*n+2*n+i,n*n+x,mas);
		add(n*n+2*n+i,n*n+n+y,mas);
		add(n*n+2*n+i,n*n+a1,mas);
		add(n*n+2*n+i,n*n+n+b1,mas);
		add(0,n*n+2*n+i,z);
		sum+=z;
	}
	int ans=dinic(0,T);
	printf("%d\n",sum-ans);
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 8ms, 内存消耗: 620K, 提交时间: 2019-05-04 12:40:01

#include<bits/stdc++.h>
using namespace std;const int N=3e3+7,inf=1e9+7;
struct data{int to,next,v;}e[N*20];int head[N],cnt=1,h[N],ans,t,w,q[N],S,T,n,m,i,j,a1,b1,a2,b2,a[50],b[50],mp[50][50];
void ins(int u,int v,int w){e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;e[cnt].v=w;}
void insert(int u,int v,int w){ins(u,v,w);ins(v,u,0);}
bool bfs(){
	memset(h,-1,sizeof(h));t=0;w=1;q[0]=S;h[S]=0;
	while(t!=w){
		int x=q[t++];
		for(int i=head[x];i;i=e[i].next)if(h[e[i].to]==-1&&e[i].v)
		q[w++]=e[i].to,h[e[i].to]=h[x]+1;
	}return h[T]!=-1;
}
int dfs(int x,int f){
	if(x==T)return f;
	int w,used=0;
	for(int i=head[x];i;i=e[i].next)if(e[i].v&&h[e[i].to]==h[x]+1){
		w=dfs(e[i].to,min(f-used,e[i].v));
		used+=w;e[i].v-=w;e[i^1].v+=w;
		if(used==f)return f;
	}if(!used)h[x]=-1;
	return used;
}
int dinic(int ans=0){while(bfs())ans+=dfs(S,inf);return ans;}
int id(int x,int y){return 2*n+(x-1)*n+y;}
int main(){
	for(scanf("%d%d",&n,&m),S=n*2+n*n+m+1,T=S+1,i=1;i<=n;++i)for(j=1;j<=n;++j)scanf("%d",&mp[i][j]),ans+=mp[i][j];
	for(i=1;i<=n;++i)scanf("%d",a+i),insert(i,T,a[i]);for(i=1;i<=n;++i)scanf("%d",b+i),insert(n+i,T,b[i]);
	for(i=1;i<=n;++i)for(j=1;j<=n;++j)insert(S,id(i,j),mp[i][j]),insert(id(i,j),i,inf),insert(id(i,j),n+j,inf);
	for(i=1;i<=m;++i)
	scanf("%d%d%d%d%d",&a1,&b1,&a2,&b2,&w),insert(S,n*2+n*n+i,w),ans+=w,
	insert(n*2+n*n+i,id(a1,b1),inf),insert(n*2+n*n+i,id(a2,b2),inf);
	printf("%d\n",ans-dinic());
}

详情