Flandre Scarlet's Blog

伏地膜__shi%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

题意：一段1中有两段0= =（比如这个100111000011111）

以及n个操作：将[li,ri]上的数取反，代价为ri-li+1

求数列全变为1的最小代价。

考场上写了个25的爆搜。顺便%%%ZHL大爷160Rank1

注意到原数列段数很少。差分：（和前一位异或，第零位视作1）

100111000011111

↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓

010100100010000

则

操作2 3的效果：a[2]^=1,a[4]^=1

操作2 6的效果：a[2]^=1,a[7]^=1

操作4 10的效果：a[4]^=1,a[11]^=1

最终要求：全0

若要取反L,R之间的数，使用的操作则构成连L与R+1上的路径【卧槽蒟蒻怎么想得到QAQ】

于是所有操作对应连边跑最短路，连离散化都不需要。

注意这里最短路不同的起点、终点组有三组，故窝乱搞了一下。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<queue>
#define maxn 500010
#define INF 2000000000
using namespace std;
struct Edge
{
	int f,t,w;
};
int first[maxn],Next[maxn],n;
vector<Edge> ES;
void AddEdge(int f,int t,int w)
{
	int m=ES.size();
	ES.push_back((Edge){f,t,w});
	Next[m]=first[f];
	first[f]=m;
}
long long dis[maxn];
int inq[maxn];
queue <int> Q;
void SPFA(int s,long long& aa,long long &bb,long long &cc)
{
	for (int i=1;i<=500001;i++)
	{
		dis[i]=(long long)INF*1000000;
	}
	dis[s]=0;
	Q.push(s);
	inq[s]=1;
	while (!Q.empty())
	{
		int u=Q.front();
		Q.pop();
		inq[u]=0;
		for (int i=first[u];i!=-1;i=Next[i])
		{
			Edge e=ES[i];
			if (dis[e.t]>dis[u]+e.w)
			{
				dis[e.t]=dis[u]+e.w;
				if (!inq[e.t])
				{
					inq[e.t]=1;
					Q.push(e.t);
				}
			}
		}
	}
	aa=dis[aa];
	bb=dis[bb];
	cc=dis[cc];
}
int main()
{
	int a,b,c,d,e;
	while (scanf("%d%d%d%d%d",&a,&b,&c,&d,&e)!=EOF)//多组数据
	{
		ES.clear(); 
		scanf("%d",&n);
		memset(first,-1,sizeof(first));
		for (int i=1;i<=n;i++)
		{
			int l,r;
			scanf("%d %d",&l,&r);
			AddEdge(l,r+1,r+1-l);
			AddEdge(r+1,l,r+1-l);
		}
		long long a1=a+b+1,a2=a+b+c+1,a3=a+b+c+d+1,b1=a+1,b2=a+b+c+1,b3=a+b+c+d+1,c1=a+1,c2=a+b+1,c3=a+b+c+d+1;
		SPFA(a+1,a1,a2,a3);	
		SPFA(a+b+1,b1,b2,b3);
		SPFA(a+b+c+1,c1,c2,c3);
		long long ans=a1+c3;
		ans=min(ans,a2+b3);
		ans=min(ans,a3+b2);
		if (ans>=(long long)INF*1000000) ans=-1;
		printf("%lld\n",ans);		
	}
	return 0;
}