loj6225「网络流 24 题」火星探险问题

()
题目描述

火星探险队的登陆舱将在火星表面着陆，登陆舱内有多部障碍物探测车。

登陆舱着陆后，探测车将离开登陆舱向先期到达的传送器方向移动。

探测车在移动中还必须采集岩石标本。

每一块岩石标本由最先遇到它的探测车完成采集。

每块岩石标本只能被采集一次。

岩石标本被采集后，其他探测车可以从原来岩石标本所在处通过。

探测车不能通过有障碍的地面。

本题限定探测车只能从登陆处沿着向南或向东的方向朝传送器移动，而且多个探测车可以在同一时间占据同一位置。

如果某个探测车在到达传送器以前不能继续前进，则该车所采集的岩石标本将全部损失。

用一个 P×Q\text{P}\times \text{Q}P×Q 网格表示登陆舱与传送器之间的位置。登陆舱的位置在 (X1,Y1)(X_1,Y_1)(X​1​​,Y​1​​) 处，传送器 的位置在 (XP,YQ)(X_P,Y_Q)(X​P​​,Y​Q​​) 处。 给定每个位置的状态，计算探测车的最优移动方案，使到达传送器的探测车的数量最多， 而且探测车采集到的岩石标本的数量最多。

233
输入格式

文件的第一行为探测车数 car\text{car}car ，第二行为 P\text{P}P 的值，第三行为 Q\text{Q}Q 的值。

接下来的 Q\text{Q}Q 行是表示登陆舱与传送器之间的位置状态的 P×Q\text{P}\times \text{Q}P×Q 网格。

用三个数字表示火星表面位置的状态：0 表示平坦无障碍，1表示障碍，2 表示石块。
输出格式

程序运行结束时，输出每个探测车向传送器移动的序列。

每行包含探测车号和一个移动方向，0 表示向南移动，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 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

数据范围与提示

1≤P,Q,car≤351\leq P,Q,\text{car}\leq 351≤P,Q,car≤35

我把每个点都拆成两个点 所有两个点之间都给费用0 流量无限的边表示这个点可以随意经过 限制费用为了限制采石头的次数 如果这个点有可采集的那我就添加费用1 流量1的边 否则不添加 然后跑最大费用最大流

我输出方案的时候一定只有最大流个机器人可以到达 我就dfs即可 dfs 的时候针对一个机器人 我只需要找到一个可行路径就可以 不需要把所有路径完全搜索

#include<queue> 
#include<cstdio>
#include<cstring>
#include<algorithm>
#define inf 0x3f3f3f3f
#define N 3200
using namespace std;
inline char gc(){
    static char now[1<<16],*S,*T;
    if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
    return *S++;
}
inline int read(){
    int x=0;char ch=gc();
    while(ch<'0'||ch>'9') ch=gc();
    while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();}
    return x;
}bool flag[N];
int car,p,q,num=1,dx[]={0,1},dy[]={1,0},T,f[N],path[N],pre[N],h[N],id[40][40],mp[40][40],tot,nn;
struct node{
    int y,next,z,c;
}data[N*N];
inline void insert1(int x,int y,int z,int c){
    data[++num].y=y;data[num].z=z;data[num].next=h[x];h[x]=num;data[num].c=c;
    data[++num].y=x;data[num].z=0;data[num].next=h[y];h[y]=num;data[num].c=-c;
}
inline bool spfa(){
    queue<int>q;memset(f,128,sizeof(f));memset(flag,0,sizeof(flag));memset(pre,-1,sizeof(pre));flag[0]=1;f[0]=0;q.push(0);
    while(!q.empty()){
        int x=q.front();q.pop();flag[x]=0;
        for (int i=h[x];i;i=data[i].next){
            int y=data[i].y,z=data[i].z,c=data[i].c;
            if (f[x]+c>f[y]&&z){
                f[y]=f[x]+c;pre[y]=x;path[y]=i;
                if (!flag[y]) flag[y]=1,q.push(y);
            }
        }
    }if (pre[T]==-1) return 0;else return 1;
}
inline void dfs(int id,int x){
    if (x==tot) return;
    for (int i=h[x+nn];i;i=data[i].next){
        if(i&1||!data[i^1].z) continue;int y=data[i].y;
        if (x%p==y%p) printf("%d 0\n",id);else printf("%d 1\n",id);
        data[i].z+=1;data[i^1].z-=1;dfs(id,y);return;
    }
}
int main(){
    freopen("loj.in","r",stdin);
    car=read();p=read();q=read();tot=0;nn=p*q;T=nn<<1;
    for (int i=1;i<=q;++i)
        for(int j=1;j<=p;++j) id[i][j]=++tot,mp[i][j]=read();
    for (int i=1;i<=q;++i){
        for (int j=1;j<=p;++j){
            if (mp[i][j]==1) continue;insert1(id[i][j],id[i][j]+nn,inf,0);
            if (mp[i][j]==2) insert1(id[i][j],id[i][j]+nn,1,1);
            for (int k=0;k<2;++k){
                int x1=i+dx[k],y1=j+dy[k];
                if (x1>q||y1>p||mp[x1][y1]==1) continue;
                insert1(id[i][j]+nn,id[x1][y1],inf,0);
            }
        }
    }insert1(0,1,car,0);int ans=0;
//  for (int i=2;i<=num;++i) printf("%d %d %d\n",data[i].y,data[i].z,data[i].c);
    while(spfa()){
        int minn=inf,now=T;
        while(now) minn=min(minn,data[path[now]].z),now=pre[now];now=T;ans+=minn;
        while(now) {data[path[now]].z-=minn;data[path[now]^1].z+=minn;now=pre[now];}
    }//printf("%d\n",ans);
    for (int i=1;i<=ans;++i) dfs(i,1);
    return 0;
}