题目分类：网络流

两道网络流题一起写了。

玩具兵题意：

给出一个每个格子有高度的矩阵，有k个步兵k个骑兵1个天兵，骑兵只能从高到低，步兵只能从低到高，天兵随意，现在给出初始状态和最终状态，初始状态兵种指定，最终状态兵种不作要求，使得每个格子满足一定的数量，允许使用超能力，每次超能力可以交换任意多对兵，球最少超能力使用数。

题解：

可以发现交换兵就是转换了兵的种类。

题意的问题在于一次超能力可以交换很多兵。

题意没问题之后可以枚举答案。

先要求出每个兵不考虑天兵时到每个终点位置需要几次超能力，这个可以通过若干遍spfa计算得到。

这样问题就转化成了二分图匹配。

接下来考虑天兵。

天兵相当于是每次使用就可以将一个兵移到对应位置，所以可以给最大匹配加上超能力数看有没有超过完备匹配来判断。

程序：

#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;
const int maxl=200000;
int st[maxl],ed;
struct node
{
    int next,to,fl,opt,stage;
}g[10*maxl];
inline void add(int x,int y,int z,int staa)
{
//	printf("%d %d %d\n",x,y,z);
    ed++;
    g[ed].to=y;
    g[ed].next=st[x];
    g[ed].fl=z;
    g[ed].opt=ed+1;
    g[ed].stage=staa;
    st[x]=ed;
    ed++;
    g[ed].to=x;
    g[ed].next=st[y];
    g[ed].fl=0;
    g[ed].opt=ed-1;
    g[ed].stage=staa;
    st[y]=ed;
}
int x1,x2,x3,lev[maxl],des,gap;
inline bool makelev()
{
    queue<int>q;
    q.push(0);
    memset(lev,-1,sizeof(lev));
    lev[0]=1;
    while (!q.empty())
    {
        x1=q.front();q.pop();//printf("%d ",x1);
        for (int i=st[x1];i!=0;i=g[i].next)
        {
            if(g[i].stage<=gap&&lev[g[i].to]==-1&&g[i].fl!=0)
            {
                q.push(g[i].to);
                lev[g[i].to]=lev[x1]+1;
                if(g[i].to==des){return true;}
            }
        }
    }return false;
}
int stap,sta[maxl],spre[maxl],stae[maxl];
int maxflow;
inline void extend()
{
    int del;
    stap=1;
    sta[1]=0;
    for (int i=0;i<=des;i++)
    {
        spre[i]=st[i];//printf("%d %d\n",i,st[i]);
    }
    while (stap!=0)
    {
        x1=sta[stap];
    //  printf("%d\n",x1);
        if(x1!=des)
        {
            for (;spre[x1]!=0;spre[x1]=g[spre[x1]].next)
            {
                if(g[spre[x1]].stage<=gap&&g[spre[x1]].fl!=0&&lev[x1]+1==lev[g[spre[x1]].to])
                {
                    break;
                }
            }
            if(spre[x1]!=0)
            {
                stap++;
                stae[stap]=spre[x1];
                sta[stap]=g[spre[x1]].to;
            }
            else
            {
                stap--;lev[x1]=0;
            }
        }
        else
        {
            del=1050000000;
            for (int i=stap;i>=2;i--)
            {
                del=min(del,g[stae[i]].fl);
            }//printf("%d\n",del);
            maxflow+=del;
            for (int i=stap;i>=2;i--)
            {
                g[stae[i]].fl-=del;
                g[g[stae[i]].opt].fl+=del;
                if(g[stae[i]].fl==0)stap=i-1;
            }
        }
    }
}
inline void dinic()
{
    while (makelev())extend();
}
int dis[120][120];
int n,m,k,hei[120][120],T,va[1200],inq[120][120];
pair<int,int>a[1200],b[1200],c[1200];
const int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
inline bool inside(int x,int y)
{
	if(x>0&&x<=n&&y>0&&y<=m)return true;
	return false;
}
inline int cost(int x11,int y11,int x21,int y21,int vv)
{
	if(vv==0)
	{
	//	printf("%d %d %d %d %d %d %d\n",x11,y11,x21,y21,vv,hei[x11][y11],hei[x21][y21]);
		if(hei[x11][y11]>hei[x21][y21])return 1;
		return 0;
	}
	else
	{
		if(hei[x11][y11]<hei[x21][y21])return 1;
		return 0;
	}
}
inline void bfs(int x,int y,int v)
{
	queue<pair<int,int> >q;
	q.push(make_pair(x,y));
	memset(dis,1,sizeof(dis));
	memset(inq,0,sizeof(inq));
	dis[x][y]=0;
	inq[x][y]=1;
	while (!q.empty())
	{
		x1=q.front().first;
		x2=q.front().second;
		inq[x1][x2]=0;
		for (int i=0;i<4;i++)
		{
			if(!inside(x1+dir[i][0],x2+dir[i][1]))continue;
		//	printf("%d %d %d %d\n",x1,x2,x1+dir[i][0],x2+dir[i][1]);
			int cc=cost(x1,x2,x1+dir[i][0],x2+dir[i][1],(v^(dis[x1][x2]&1)));//printf("%d\n",cc);
	//		printf("%d %d %d %d %d\n",x1,x2,x1+dir[i][0],x2+dir[i][1],cc);
	//		system("pause");
			if(dis[x1+dir[i][0]][x2+dir[i][1]]>dis[x1][x2]+cc)
			{
				dis[x1+dir[i][0]][x2+dir[i][1]]=dis[x1][x2]+cc;
				if(inq[x1+dir[i][0]][x2+dir[i][1]]==0)
				{
					inq[x1+dir[i][0]][x2+dir[i][1]]=1;
					q.push(make_pair(x1+dir[i][0],x2+dir[i][1]));
				}
			}
		}
		q.pop();
	}
}
int main()
{
	scanf("%d %d %d %d",&n,&m,&k,&T);
	des=T+k+k+1;
	for (int i=1;i<=k;i++)
	{
		add(0,i,1,0);
		scanf("%d %d",&a[i].first,&a[i].second);
	}
	for (int i=1;i<=k;i++)
	{
		add(0,i+k,1,0);
		scanf("%d %d",&b[i].first,&b[i].second);
	}
	scanf("%d %d",&x1,&x2);
	for (int i=1;i<=T;i++)
	{
		scanf("%d %d %d",&c[i].first,&c[i].second,&va[i]);
		add(k+k+i,des,va[i],0);
	}
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++)
		{
			scanf("%d",&hei[i][j]);
		}
	}
	for (int i=1;i<=k;i++)
	{
		bfs(a[i].first,a[i].second,0);
		for (int j=1;j<=T;j++)
		{
			add(i,k+k+j,1,dis[c[j].first][c[j].second]);
		}/*printf("\n");
		for (int i1=1;i1<=n;i1++)
		{
			for (int j1=1;j1<=m;j1++)
			{
				printf("%d ",dis[i1][j1]);
			}printf("\n");
		}printf("\n");*/
	}
	for (int i=1;i<=k;i++)
	{
		bfs(b[i].first,b[i].second,1);
		for (int j=1;j<=T;j++)
		{
			add(i+k,k+k+j,1,dis[c[j].first][c[j].second]);
		}
	}//printf("----------------------------------");
	for (gap=0;gap<=2*k;gap++)
	{
		dinic();//printf("%d %d\n",gap,maxflow);
		if(maxflow+gap>=2*k)break;
	}printf("%d\n",gap);
	return 0;
}

a+bproblem题意：

给出一行格子，可以进行黑白染色。

每个格子染成白色获得一个权值，染成黑色获得一个权值。

每个格子有额外的三个权值li，ri，ai

对于一个格子，如果有格子j满足j<i，li<=ai<=ri，i为黑色j为白色

就称之为奇怪的格子并损失一个额外的权值。

球最优染色方案。

题解：

先考虑没有奇怪的格子，可以发现是最小割模型

考虑节点i如果属于S割就是黑色，属于T割就是白色。

同时要考虑求的是最大值，所以把收获的权值改为失去的损失

然后可以对每个i新建节点i+n，由i+n像每个满足条件的j连边正无穷，表示如果j在T割那么i+n一定在T割，这样就能明白i到i+n的边一定是作为奇怪的方格需要损失的权值。

发现这样会最多连出n平方条边，会超时超空间。

所以考虑将li到ri的区间画到线段树上，这样就只有logn部分了，每个i向ai对应的叶子连边，每个线段树内节点向左右儿子连边，每个i+n向线段树上li到ri的不相交区间们连边，权值均为正无穷。

但是发现还需要满足j<i的要求，于是使用可持久化线段树。

同时发现如果ai相等会不好办，在ai相等的情况下从新节点向旧节点连边权值正无穷。

就这样就行了

一开始居然忘了离散化li和ri

然后在给叶子节点连边的时候直接连给了ai也是粗心错误

程序：

最后跑得比shanquan2还快一点是什么情况

#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<map>
using namespace std;
const int maxl=200000;
int st[maxl],ed;
struct node
{
    int next,to,fl,opt;
}g[5*maxl];
int deps;
const int inf=1050000000;
inline void add(int x,int y,int z)
{
//	printf("%d %d %d\n",x,y,z);
	deps=max(deps,x);
	deps=max(deps,y);
    ed++;
    g[ed].to=y;
    g[ed].next=st[x];
    g[ed].fl=z;
    g[ed].opt=ed+1;
    st[x]=ed;
    ed++;
    g[ed].to=x;
    g[ed].next=st[y];
    g[ed].fl=0;
    g[ed].opt=ed-1;
    st[y]=ed;
}
int x1,x2,x3,lev[maxl],des,gap;
inline bool makelev()
{
    queue<int>q;
    q.push(0);
    memset(lev,-1,sizeof(lev));
    lev[0]=1;
    while (!q.empty())
    {
        x1=q.front();q.pop();//printf("%d ",x1);
        for (int i=st[x1];i!=0;i=g[i].next)
        {
            if(lev[g[i].to]==-1&&g[i].fl!=0)
            {
                q.push(g[i].to);
                lev[g[i].to]=lev[x1]+1;
                if(g[i].to==des){return true;}
            }
        }
    }return false;
}
int stap,sta[maxl],spre[maxl],stae[maxl];
int maxflow;
inline void extend()
{
    int del;
    stap=1;
    sta[1]=0;
    for (int i=0;i<=deps;i++)
    {
        spre[i]=st[i];//printf("%d %d\n",i,st[i]);
    }
    while (stap!=0)
    {
        x1=sta[stap];
    //  printf("%d\n",x1);
        if(x1!=des)
        {
            for (;spre[x1]!=0;spre[x1]=g[spre[x1]].next)
            {
                if(g[spre[x1]].fl!=0&&lev[x1]+1==lev[g[spre[x1]].to])
                {
                    break;
                }
            }
            if(spre[x1]!=0)
            {
                stap++;
                stae[stap]=spre[x1];
                sta[stap]=g[spre[x1]].to;
            }
            else
            {
                stap--;lev[x1]=0;
            }
        }
        else
        {
            del=1050000000;
            for (int i=stap;i>=2;i--)
            {
                del=min(del,g[stae[i]].fl);
            }//printf("%d\n",del);
            maxflow+=del;
            for (int i=stap;i>=2;i--)
            {
                g[stae[i]].fl-=del;
                g[g[stae[i]].opt].fl+=del;
                if(g[stae[i]].fl==0)stap=i-1;
            }
        }
    }
}
inline void dinic()
{
    while (makelev())extend();
}
int a[12000],b[12000],w[12000],r[12000],l[12000],p[12000];
int n;
struct segemtn
{
	int les[220000],ris[220000],lef[220000],rig[220000],root[220000],siz,cnt,val[220000];
	inline void build(int x,int le,int ri)
	{
		lef[x]=le;
		rig[x]=ri;
		if(le==ri)return;
		siz++;
		les[x]=siz;
		build(les[x],le,(le+ri)/2);
		siz++;
		ris[x]=siz;
		build(ris[x],(le+ri)/2+1,ri);
		add(x+20000,les[x]+20000,inf);
		add(x+20000,ris[x]+20000,inf);//printf("-----------%d %d %d\n",x,le,ri);
	}
	inline void build(int le,int ri)
	{
		siz++;
		root[0]=siz;
		build(1,le,ri);
	}
	inline void edit(int x,int las,int pos,int de)
	{
	//	printf("+++++++++:%d %d %d %d %d\n",x,las,pos,lef[x],rig[x]);
		if(lef[x]==rig[x])
		{
			val[x]=val[las]+1;
			add(x+20000,de,inf);
			if(val[las]!=0)add(x+20000,las+20000,inf);
			return;
		}
		if(pos<=rig[les[las]])
		{
			siz++;
			les[x]=siz;
			ris[x]=ris[las];
			lef[les[x]]=lef[les[las]];
			rig[les[x]]=rig[les[las]];
			edit(les[x],les[las],pos,de);
		}
		else
		{
			siz++;
			ris[x]=siz;
			les[x]=les[las];
			rig[ris[x]]=rig[ris[las]];
			lef[ris[x]]=lef[ris[las]];
			edit(ris[x],ris[las],pos,de);
		}
		val[x]=val[les[x]]+val[ris[x]];
		add(x+20000,les[x]+20000,inf);
		add(x+20000,ris[x]+20000,inf);
	}
	inline void edit(int pos,int de)
	{
		cnt++;
		siz++;
		root[cnt]=siz;
		lef[root[cnt]]=lef[root[cnt-1]];
		rig[root[cnt]]=rig[root[cnt-1]];
		edit(root[cnt],root[cnt-1],pos,de);
	}
	inline void query(int x,int le,int ri,int de)
	{
	//	printf("%d %d %d %d %d %d\n",x,le,ri,de,lef[x],rig[x]);
		if(le<=lef[x]&&ri>=rig[x])
		{
			add(de,20000+x,inf);
			return;
		}
		if(le<=rig[les[x]])query(les[x],le,ri,de);
		if(ri>=lef[ris[x]])query(ris[x],le,ri,de);
	}
	inline void query(int x,int le,int ri)
	{
		query(root[x],le,ri,x+1+n);
	}
}sgt;
map<int,int>hash;
int tp[120000],ans;
int main()
{
	scanf("%d",&n);
	des=n+n+1;
	for (int i=1;i<=n;i++)
	{
		scanf("%d %d %d %d %d %d",&a[i],&b[i],&w[i],&l[i],&r[i],&p[i]);
		add(0,i,b[i]);
		add(i,i+n,p[i]);
		tp[i]=a[i];
		ans+=b[i];
		ans+=w[i];
		add(i,des,w[i]);
	}
	sort(tp+1,tp+n+1);
	for (int i=1;i<=n;i++)
	{
		//printf("%d %d %d %d\n",i,a[i],l[i],r[i]);
		a[i]=lower_bound(tp+1,tp+n+1,a[i])-(tp);
		l[i]=lower_bound(tp+1,tp+n+1,l[i])-(tp);
		r[i]=upper_bound(tp+1,tp+n+1,r[i])-(tp)-1;
	//	printf("%d %d %d\n",a[i],l[i],r[i]);
	}
	sgt.build(1,n);
	for (int i=1;i<=n;i++)
	{
		if(l[i]<=r[i])sgt.query(i-1,l[i],r[i]);
		sgt.edit(a[i],i);
	}
	dinic();
	printf("%d\n",ans-maxflow);
	return 0;
}
/*
10
0 1 7 3 9 2
7 4 0 9 10 5
1 0 4 2 10 2
7 9 1 5 7 2
6 3 5 3 6 2
6 6 4 1 8 1
6 1 6 0 6 5
2 2 5 0 9 3
5 1 3 0 2 5
 5 6 7 1 1 2
*/