「dwjshift毒瘤模拟赛」path - 平面图最短路转最小割 （毒瘤，未AC）

题目大意

    给出一个包含$n+1$个结点的有向图，结点的编号为$0$到$n$。图中有$m$条有向边，第$i$条有向边起点为$u_i$，终点为$v_i$，且长度为$w_i$。并且这些边还满足如下的性质：

• 对任意一条边，满足 $u_i\lt v_i$。
• 不存在两条边$i,j$使得$u_i<u_j<v_i<v_j$。除了结点$0$和结点$n$以外，其余的每个结点都有颜色。现在需要你找出一条从结点$0$走到结点$n$的最短路径。对于任意一种颜色，这条路径要么经过了这种颜色的所有结点，要么就不经过这种颜色的任意一个结点。如果不存在这样的路径，请输出$-1$，否则输出最短路径的长度。

---

题目分析

因为题目保证不存在$u_i<u_j<v_i<v_j$，故这是一个平面图。
带有这种限制的最短路很不好做，考虑转成对偶图最小割。

先把不可能经过的点删掉，样例二长这个样子。

然后把不可能完全经过的颜色全部删掉。
剩下的如图是一棵树。
每个对偶图上的点管辖其树上的后代所不管辖原图上的点。
割哪条边就走哪条边。
注意树上要连反向INF边表示不能割了父亲再割儿子。

怎么限制颜色呢？
每个对偶图的点向其管辖的原图点对应的“颜色点”连INF双向边。

原题题解部分是错的，原题数据第一组是错的。
也不知道我哪儿写错了，除开第一组持续80分。

---

代码

#include<bits/stdc++.h>

using namespace std;

#define inf INT_MAX/3

inline int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
	while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
	return num*bj;
}

const int maxn=2005;

struct Dinic {
	struct Edge {
		int from,to,cap,flow;
		Edge(int x=0,int y=0,int c=0,int f=0):from(x),to(y),cap(c),flow(f) {}
	};
	int n,m,s,t;
	vector<Edge>edges;
	vector<int>G[maxn];
	bool vst[maxn];
	int dist[maxn],cur[maxn];
	void init(int n) {
		this->n=n;
		edges.clear();
		for(int i=1; i<=n; i++)G[i].clear();
	}
	void AddEdge(int x,int y,int v1,int v2) {
		edges.push_back(Edge(x,y,v1,0));
		edges.push_back(Edge(y,x,v2,0));
		m=edges.size();
		G[x].push_back(m-2);
		G[y].push_back(m-1);
	}
	bool bfs() {
		fill(vst+1,vst+n+1,0);
		queue<int>Q;
		Q.push(t);
		vst[t]=1;
		while(!Q.empty()) {
			int Now=Q.front();
			Q.pop();
			for(int id:G[Now]) {
				Edge& e=edges[id^1];
				int Next=e.from;
				if(!vst[Next]&&e.cap>e.flow) { 
					vst[Next]=1;
					dist[Next]=dist[Now]+1;
					if(Next==s)return 1;
					Q.push(Next);
				}
			}
		}
		return vst[s];
	}
	int dfs(int Now,int a) {
		if(Now==t||a==0)return a;
		int flow=0;
		for(int& i=cur[Now]; i<G[Now].size(); i++) {
			Edge& e=edges[G[Now][i]];
			int Next=e.to;
			if(dist[Now]-1!=dist[Next])continue;
			int nextflow=dfs(Next,min(a,e.cap-e.flow));
			if(nextflow>0) {
				e.flow+=nextflow;
				edges[G[Now][i]^1].flow-=nextflow;
				flow+=nextflow;
				a-=nextflow;
				if(a==0)break;
			}
		}
		return flow;
	}
	int maxflow(int s,int t) {
		this->s=s;
		this->t=t;
		int flow=0;
		while(bfs()) {
			memset(cur,0,sizeof(cur));
			flow+=dfs(s,inf);
		}
		return flow;
	}
} dinic;

struct Edge {
	int from,to,dist;
	Edge(int x=0,int y=0,int v=0):from(x),to(y),dist(v) {}
	bool operator < (const Edge &b) const {return from<b.from||(from==b.from&&to>b.to);}
} edge[maxn],tmp[maxn];

vector<int> edges[maxn],fedges[maxn];
int n,m,a[maxn],Max=0;
bool vst1[maxn],vst2[maxn],del[maxn];

void Dfs1(int Now) {
	vst1[Now]=1;
	for(int Next:edges[Now])if(!vst1[Next])Dfs1(Next);
}

void Dfs2(int Now) {
	vst2[Now]=1;
	for(int Next:fedges[Now])if(!vst2[Next])Dfs2(Next);
}

int main() {
	n=Get_Int();
	m=Get_Int();
	for(int i=1; i<n; i++)a[i]=Get_Int(),Max=max(Max,a[i]);
	for(int i=1; i<=m; i++) {
		int x=Get_Int(),y=Get_Int(),v=Get_Int();
		tmp[i]=Edge(x,y,v);
		edges[x].push_back(y);
		fedges[y].push_back(x);
	}
	Dfs1(0);
	Dfs2(n);
	for(int i=1; i<=n; i++)if(!vst1[i]||!vst2[i])del[a[i]]=1;
	int tot=0;
	for(int i=1; i<=m; i++)if(!del[a[tmp[i].from]]&&!del[a[tmp[i].to]])edge[++tot]=tmp[i];
	m=tot;
	edge[++m]=Edge(0,n,0);
	sort(edge+1,edge+m+1);
	int S=1,T=m+Max+1;
	dinic.init(T);
	for(int i=1; i<=m; i++) {
		int last=edge[i].from,j=i+1;
		while(true) {
			while(edge[j].from<last&&j<=m)j++;
			if(j>m||edge[j].to>edge[i].to)break;
			dinic.AddEdge(i,j,edge[j].dist,inf);
			last=edge[j].to;
			if(last!=edge[i].to) {
				dinic.AddEdge(i,m+a[last],inf,inf);
				dinic.AddEdge(m+a[last],i,inf,inf);
			}
		}
		if(last==edge[i].from)dinic.AddEdge(i,T,inf,0);
	}
	int ans=dinic.maxflow(S,T);
	printf("%d\n",ans==inf?-1:ans);
	return 0;
}