火星探险问题

题目描述
火星探险队的登陆舱将在火星表面着陆，登陆舱内有多部障碍物探测车。登陆舱着陆后，探测车将离开登陆舱向先期到达的传送器方向移动。探测车在移动中还必须采集岩石标本。每一块岩石标本由最先遇到它的探测车完成采集。每块岩石标本只能被采集一次。岩石标本被采集后，其他探测车可以从原来岩石标本所在处通过。探测车不能通过有障碍的地面。本题限定探测车只能从登陆处沿着向南或向东的方向朝传送器移动，而且多个探测车可以在同一时间占据同一位置。如果某个探测车在到达传送器以前不能继续前进，则该车所采集的岩石标本将全部损失。

用一个 P·Q 网格表示登陆舱与传送器之间的位置。登陆舱的位置在(X1,Y1)处，传送器

的位置在(XP ,YQ)处。

X 1,Y 1 X 2 , Y 1 X 3 , Y 1 … X P-1, Y 1 X P , Y 1

X 1,Y 2 X 2 , Y 2 X 3 , Y 2 … X P-1, Y 2 X P , Y 2

X 1, Y 3 X 2 , Y 3 X 3 ,Y 3 … X P-1, Y 3 X P , Y 3

… …

X 1 ,Y Q-1 X 2 , Y Q-1 X 3 , Y Q-1 … X P-1, Y Q-1 X P , Y Q-1

X 1,Y Q X 2 , Y Q X 3 , Y Q … X P-1, Y Q X P ,Y Q

给定每个位置的状态，计算探测车的最优移动方案，使到达传送器的探测车的数量最多，

而且探测车采集到的岩石标本的数量最多

输入格式
第 1行为探测车数，第 2 行为 P 的值，第3 行为Q 的值。接下来的 Q 行是表示登陆舱与传送器之间的位置状态的 P·Q 网格。用 3 个数字表示火星表面位置的状态：0 表示平坦无障碍，1表示障碍，2 表示石块。

输出格式
每行包含探测车号和一个移动方向，0 表示向南移动，1 表示向东移动。

输入输出样例
输入 #1 复制
2
10
8
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 1 0 0 0
0 0 0 1 0 2 0 0 0 0
1 1 0 1 2 0 0 0 0 1
0 1 0 0 2 0 1 1 0 0
0 1 0 1 0 0 1 1 0 0
0 1 2 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0
输出 #1 复制
1 1
1 1
1 1
1 1
1 0
1 0
1 1
1 1
1 1
1 1
1 0
1 0
1 1
1 0
1 0
1 0
2 1
2 1
2 1
2 1
2 0
2 0
2 0
2 0
2 1
2 0
2 0
2 1
2 0
2 1
2 1
2 1
说明/提示
车数,P,Q<=35

因为每个石块只会被采集一次，所以很明显的拆点限制采集。但是当时我写的时候想到如果我们对于每个点，连出去的时候连一条流量为1，费用为（当前点==石块），再加一条流量为INF,费用为0的边（很***是吧。。。。。因为每个点会连出去两次，所以可能被用两次。。。。QAQ。。所以还是要拆点）。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=32000,M=1000010;
const int inf=0x3f3f3f3f;
int num,n,m,g[40][40],s,t,v[N],e[N],d[N],maxflow,base;
int head[N],nex[M],to[M],w[M],flow[M],tot=1;
inline void ade(int a,int b,int c,int d){
	to[++tot]=b; w[tot]=d; flow[tot]=c; nex[tot]=head[a]; head[a]=tot;
}
inline void add(int a,int b,int c,int d){
	ade(a,b,c,d);	ade(b,a,0,-d);
}
inline int id(int x,int y){
	return (x-1)*m+y;
}
int spfa(){
	memset(d,0xcf,sizeof d);	queue<int> q;	q.push(s);
	int vis[N]={0};	d[s]=0;	vis[s]=1;
	while(q.size()){
		int u=q.front();	q.pop();	vis[u]=0;
		for(int i=head[u];i;i=nex[i]){
			if(flow[i]&&d[to[i]]<d[u]+w[i]){
				d[to[i]]=d[u]+w[i];
				v[to[i]]=u; e[to[i]]=i;
				if(!vis[to[i]])	q.push(to[i]),vis[to[i]]=1;
			}
		}
	}
	return d[t]!=0xcfcfcfcf;
}
void EK(){
	while(spfa()){
		int mi=inf;
		for(int i=t;i!=s;i=v[i])	mi=min(mi,flow[e[i]]);
		for(int i=t;i!=s;i=v[i])	flow[e[i]]-=mi,flow[e[i]^1]+=mi; 
		maxflow+=mi;
	}
}
void out(int p,int x){
	for(int i=head[x+base];i;i=nex[i]){
		if(flow[i^1]&&to[i]!=t&&x<to[i]){
			flow[i^1]--;	cout<<p<<' ';
			if(to[i]==1+x)	cout<<1<<endl;	else	cout<<0<<endl;
			return out(p,to[i]);
		}
	}
}
signed main(){
	cin>>num>>m>>n;	s=0;	t=2*n*m+1;	add(s,1,num,0);	base=n*m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			int x;	cin>>x;	if(x==1)	continue;
			add(id(i,j),id(i,j)+base,1,x);
			add(id(i,j),id(i,j)+base,inf,0);
			if(i+1<=n)	add(id(i,j)+base,id(i+1,j),inf,0);
			if(j+1<=m)	add(id(i,j)+base,id(i,j+1),inf,0);
		}
	}
	add(id(n,m)+base,t,num,0);
	EK();
	for(int i=1;i<=maxflow;i++)	out(i,1);
	return 0;
}