[BJOI2016]水晶做题心得

这是一个写了我两小时的傻逼题。写这个题浪费了一堆时间后，我才意识到我码力又不行了。于是整理起了实现技巧，开始练码力。

思路

不难。首先把 \((x,y,z)\) 变成 \((x-z,y-z)\)。因为发现 \((x,y,z)\) 同时减去某个数表示的位置不变，同时减去 \(z\)，把坐标只用 \(x,y\) 来描述。

发现是关于点权的，先把每个点拆成入点和出点，连一条边表示它的点权。假设入，出点分别是 \(a_i,a_o\)

然后枚举一下每个三角形，每个直线，假设是 \((a,b,c)\)。

那么这样连边：

\(S \xrightarrow[INF]{} a_i \xrightarrow[val_a]{} a_o \xrightarrow[INF]{} b_i\xrightarrow[val_b]{} b_o\xrightarrow[INF]{} c_i\xrightarrow[val_c]{}c_o\xrightarrow[INF]{} T\)

实现问题&改进

发现这样连边会连出环来。解法是，考虑按 \((x+y)\%3\) 分类，强行钦定某个顺序。这样就不会产生环了。
分开考虑三角形和直线太麻烦了，而且非常容易写错。我因此写错了 \(114514\) 次。事实上可以一块考虑，对于每个\((x+y)\%3=0\) 的，考虑它的“六周” (“四周”这个词在本题中的引申，注意到相邻的有六个点)，不能有相邻的 \(\%3=1\) 和 \(\%3=2\) 的。

然后可以这样建，\(\%3=1\) 的接 \(S\)，\(\%3=2\) 的接 \(T\)，\(\%3=0\) 的，向周围的 \(\%3=2\) 的连一条，然后周围 \(\%3=1\) 的向它来连一条，就可以完成建图了

这样结构更加清楚，简单，不容易写挂

（是参考了一篇题解中的实现

代码

#include <bits/stdc++.h>

using namespace std;

namespace Flandre_Scarlet

{

	#define N   400005

	#define INF 600000000

	#define F(i,l,r) for(int i=l;i<=r;++i)

	#define D(i,r,l) for(int i=r;i>=l;--i)

	#define Fs(i,l,r,c) for(int i=l;i<=r;c)

	#define Ds(i,r,l,c) for(int i=r;i>=l;c)

	#define MEM(x,a) memset(x,a,sizeof(x))

	#define Tra(i,u) for(int i=G.st(u),v=G.to(i);~i;i=G.nx(i),v=G.to(i))

	#define p_b push_back

	#define sz(a) ((int)a.size())

	#define all(a) a.begin(),a.end()

	#define iter(a,p) (a.begin()+p)

	int I() {char c=getchar(); int x=0; int f=1; while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar(); while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return ((f==1)?x:-x);}

	template <typename T> void Rd(T& arg){arg=I();}

	template <typename T,typename...Types> void Rd(T& arg,Types&...args){arg=I(); Rd(args...);}

	void RA(int *p,int n) {F(i,1,n) *p=I(),++p;}

	int n;

	int x[N],y[N],c[N];

	map<pair<int,int>,int> rec,rid;

	#define rc(x,y) rec[make_pair(x,y)]

	#define ri(x,y) rid[make_pair(x,y)]

    void Input()

    {

    	n=I();

    	F(i,1,n)

    	{

    		int z; Rd(x[i],y[i],z,c[i]); c[i]*=10;

    		x[i]-=z; y[i]-=z;

    		if ((x[i]+y[i])%3==0) c[i]+=c[i]/10;

    		rc(x[i],y[i])+=c[i];

    	}

    }

    class NetworkFlow

    {

    public:

        int S,T,n;

        struct edge

        {

            int v,c,nx;

        }pool_e[4000000+2]; edge *e;

        int pool_h[N+2]; int *head;

        int pool_c[N+2]; int *cur;

        int ecnt=-1;

        void clear()

        {

            ecnt=-1;

            MEM(pool_e,-1); e=pool_e+2;

            MEM(pool_h,-1); head=pool_h+2;

            MEM(pool_c,-1); cur=pool_c+2;

            // 允许 [-1]的访问

        }

        void add(int u,int v,int c)

        {

            e[++ecnt]={v,c,head[u]}; head[u]=ecnt;

        }

        void addflow(int u,int v,int c)

        {

        	// printf("flow %d %d %d\n",u,v,c);

            add(u,v,c);

            add(v,u,0);

        }

        int& st(int u) {return head[u];}

        int& cu(int u) {return cur[u];}

        int& to(int i) {return e[i].v;}

        int& cap(int i) {return e[i].c;}

        int& nx(int i) {return e[i].nx;}

        #define Trah(i,u) for(int i=st(u),v=to(i);~i;i=nx(i),v=to(i))

        #define Trac(i,u) for(int &i=cu(u),v=to(i);~i;i=nx(i),v=to(i))

        queue<int> Q;

        int dep[N];

        bool BFS()

        {

            while(!Q.empty()) Q.pop(); F(i,1,n) dep[i]=INF;

            dep[S]=1; cur[S]=head[S]; Q.push(S);

            while(!Q.empty())

            {

                int u=Q.front(); Q.pop();

                if (u==T) return true;

                Trah(i,u) if (cap(i) and dep[v]==INF)

                {

                    dep[v]=dep[u]+1;

                    cur[v]=head[v];

                    Q.push(v);

                }

            }

            return false;

        }

        int  DFS(int u,int flow)

        {

            if (u==T) return flow;

            int ans=0;

            Trac(i,u)

            {

                if (!flow) break;

                if (cap(i) and dep[v]==dep[u]+1)

                {

                    int f=DFS(v,min(flow,cap(i)));

                    if (!f)

                    {

                        dep[v]=INF;

                    }

                    else

                    {

                        cap(i)-=f; cap(i^1)+=f;

                        flow-=f; ans+=f;

                    }

                }

            }

            return ans;

        }

        int  Dinic()

        {

            int ans=0;

            while(BFS()) ans+=DFS(S,INF);

            return ans;

        }

        NetworkFlow() {clear();}

        NetworkFlow(int s,int t,int nn) {clear(); S=s; T=t; n=nn;}

    }Nt;

    int tot=0,S=1,T=2;

    int in[N],out[N];

    void Sakuya()

    {

    	int point=0;

    	tot=2;

    	F(i,1,n) c[i]=x[i]=y[i]=0;

    	for(auto p:rec)

    	{

    		int i=p.first.first,j=p.first.second;

    		++point;

    		x[point]=i;

    		y[point]=j;

    		c[point]=rc(i,j);

    		ri(i,j)=point;

    		in[point]=++tot;

    		out[point]=++tot;

    	}

    	Nt=NetworkFlow(S,T,tot);

    	F(i,1,point)

    	{

    		int t=((x[i]+y[i])%3+3)%3;

    		if (t==1) Nt.addflow(S,in[i],INF);

    		if (t==2) Nt.addflow(out[i],T,INF);

    		else

    		{

    			int nx;

    			nx=ri(x[i]-1,y[i]-1); if (nx) Nt.addflow(out[nx],in[i],INF);

    			nx=ri(x[i]+1,y[i]); if (nx) Nt.addflow(out[nx],in[i],INF);

    			nx=ri(x[i],y[i]+1); if (nx) Nt.addflow(out[nx],in[i],INF);

    			nx=ri(x[i]+1,y[i]+1); if (nx) Nt.addflow(out[i],in[nx],INF);

    			nx=ri(x[i]-1,y[i]); if (nx) Nt.addflow(out[i],in[nx],INF);

    			nx=ri(x[i],y[i]-1); if (nx) Nt.addflow(out[i],in[nx],INF);

    		}

    		Nt.addflow(in[i],out[i],c[i]);

    	}

    	int sum=0; F(i,1,point) sum+=c[i];

    	int ans=sum-Nt.Dinic();

    	printf("%d.%d\n",ans/10,ans%10);

    }

    void IsMyWife()

    {

        Input();

        Sakuya();

    }

}

#undef int //long long

int main()

{

    Flandre_Scarlet::IsMyWife();

    getchar();

    return 0;

}

后记：两种实现的比较

原实现长达 \(220\) 行，改进实现只有 \(182\) 行。
原实现（提到过）WA了 \(114514\) 次，最高拿了 \(35\)，到现在还不知道问题在哪，没调出来，也不想调了，nmsl （暴躁）

相比较改进实现一遍就A了。

所以说，码力的提升还是很重要的。

巴特西

[BJOI2016]水晶做题心得

[BJOI2016]水晶做题心得

思路

实现问题&改进

代码

后记：两种实现的比较

最新文章

热门文章

巴特西

[BJOI2016]水晶 做题心得

[BJOI2016]水晶 做题心得

思路

实现问题&改进

代码

后记：两种实现的比较

最新文章

热门文章

[BJOI2016]水晶做题心得

[BJOI2016]水晶做题心得