萌新求助QAQ
查看原帖
萌新求助QAQ
42443
06ray楼主2018/8/24 13:06

40分,蜜汁WA。

求各位大佬找错QAQ

丑陋的代码:

// luogu-judger-enable-o2
#pragma GCC optimize(3)
#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <vector>
using namespace std;
inline int read()
{
    int n=0;
    char ch=getchar();
    while(ch>'9'||ch<'0') ch=getchar();
    while(ch>='0'&&ch<='9')
     {
         n=n*10+ch-'0';
         ch=getchar();
     }
    return n; 
}
const int MAX=0x7fffffff;
int dis[1001000];
int n,m,s,t;
int head[600100],net[600100],to[600100],cap[600100];
int cnt=1;
void add(int x,int y,int c)
{
    to[++cnt]=y;
    cap[cnt]=c;
    net[cnt]=head[x];
    head[x]=cnt;
    to[++cnt]=x;
    cap[cnt]=0;
    net[cnt]=head[y];
    head[y]=cnt;
}
int BFS()
{
     memset(dis,0,sizeof(dis));
     dis[s]=1;
     queue<int>q;
     q.push(s);
     while(!q.empty())
     {
        int v=q.front();
        q.pop();
        for(int i=head[v];i;i=net[i])
        {
        	if(dis[to[i]]==0&&cap[i]>0)
        	{
            	dis[to[i]]=dis[v]+1; 
            	q.push(to[i]);
       	 	}
        }
        
     }
     if(dis[t]>0) return 1;
     return 0;
}
int find(int x,int low)
{
    int a=0;
    if(x==t)return low;
    int sum=0;
    for(int i=head[x];i;i=net[i])
    {
    	if(dis[to[i]]==dis[x]+1&&cap[i]!=0&&(a=find(to[i],min(low,cap[i]))))
    	{
       		cap[i]-=a;
       		cap[i^1]+=a;
       		low-=a;
       		sum+=a;
       		if(low==0)
       		break;
    	}
    }  
    return sum;
}
int ans=0,tans=0;
int get(int x,int y)
{
    return (x-1)*m+y;
}
bool a[210][210];
int map[40100];
int way[2]={0,-1};
signed main()
{
    cin>>n>>m;
    s=0,t=2*n*m+1;
    int tot=0;
    int inf=0x7f;
    way[0]=-m;
    for(int i=1; i<=n; i++)
    {
    	for(int j=1; j<=m; j++)
    	{
    		int num,a,b;
    		cin>>num;
    		a=get(i,j),b=a+n*m;
    		if(!num)
    		{
    			add(s,a,inf);
    			add(a,b,inf);
            }
            if(i==1||j==1||i==n||j==m)
            {
                add(b,t,inf);
            }
            if(num>0)
            {
                add(a,b,num);
            }
            for(int k=0; k<2; k++)
            {
                int newn=a+way[k];
                if(newn>0&&newn<=n*m&&map[newn]!=-1&&num!=-1&&(!(k==1&&i==1)))
                {
                    add(b,newn,inf);
                    add(newn+n*m,a,inf);
                }
            }
            map[a]=num;
        }
    }
    while(BFS())
    {
          while(tans=find(s,0x7fffffff)) ans+=tans;
    }
    cout<<ans;
    return 0;
}

2018/8/24 13:06
加载中...