网络流24题——孤岛营救问题(状压+分层图)

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<vector>
  5 #include<stack>
  6 #include<queue>
  7 using namespace std;
  8 const int maxn=16,maxstatus=1<<10,inf=1e9;
  9 int n,m,p,k;
 10 void Swap(int &a,int &b){int t=a;a=b;b=t;}
 11 bool wall[maxn*maxn][maxn*maxn];
 12 int dis[maxstatus*maxn*maxn+maxn*maxn+1];
 13 bool inq[maxstatus*maxn*maxn+maxn*maxn+1];
 14 struct door{
 15     int x,y;
 16     door(int x,int y){this->x=x;this->y=y;}
 17 };
 18 struct Edge{
 19     int to,dis;
 20     Edge (int to,int dis){
 21         this->to=to;this->dis=dis;
 22     }
 23 };
 24 vector<Edge> G[maxstatus*maxn*maxn+maxn*maxn+1];
 25 vector<door> d[15];
 26 void add(int s,int t,int dis){
 27     G[s].push_back(Edge(t,dis));
 28     G[t].push_back(Edge(s,dis));
 29 }
 30 void build(){
 31     for(int status=0;status<(1<<p);status++){
 32         int delta=status*maxn*maxn;
 33         for(int i=1;i<=n;i++){
 34             for(int j=1;j<=m;j++){
 35                 int x=maxn*i+j,y;
 36                 if(j<m){
 37                     y=maxn*i+j+1;
 38                     if(!wall[x][y])add(delta+x,delta+y,1);
 39                 }
 40                 if(i<n){
 41                     y=maxn*(i+1)+j;
 42                     if(!wall[x][y])add(delta+x,delta+y,1);
 43                 }
 44             }
 45         }
 46         for(int i=1;i<=p;i++){
 47             if(((1<<(i-1))&status)==0)continue;
 48             for(int j=0;j<d[i].size();j++){
 49                 add(delta+d[i][j].x,delta+d[i][j].y,1);
 50             }
 51         }
 52     }
 53     for(int i=0;i<(1<<p)-1;i++){
 54         //add(i*maxn*maxn+maxn+1,(i+1)*maxn*maxn+maxn+1,0);
 55         add(i*maxn*maxn+n*maxn+m,(i+1)*maxn*maxn+n*maxn+m,0);
 56     }
 57 }
 58 int spfa(){
 59     int s=maxn+1,t=maxn*n+m;
 60     for(int i=0;i<=maxstatus*maxn*maxn+maxn*maxn;i++)dis[i]=inf;
 61     memset(inq,0,sizeof(inq));
 62     queue<int> Q;
 63     Q.push(s);
 64     inq[s]=true;
 65     dis[s]=0;
 66     while(!Q.empty()){
 67         int x=Q.front();Q.pop();
 68         inq[x]=false;
 69         for(int i=0;i<G[x].size();i++){
 70             int to=G[x][i].to;
 71             if(dis[to]>dis[x]+G[x][i].dis){
 72                 dis[to]=dis[x]+G[x][i].dis;
 73                 if(!inq[to]){
 74                     Q.push(to);inq[to];
 75                 }
 76             }
 77         }
 78     }
 79     if(dis[t]==inf)return -1;
 80     return dis[t];
 81 }
 82 int main(){
 83 //    freopen("e:\in.txt","r",stdin);
 84     while(scanf("%d%d%d",&n,&m,&p)!=EOF){
 85         for(int i=0;i<15;i++)d[i].clear();
 86         for(int i=0;i<=(1<<p)*maxn*maxn+maxn*maxn;i++)G[i].clear();
 87         memset(wall,0,sizeof(wall));
 88         int k,x1,y1,x2,y2,g,s;
 89         scanf("%d",&k);
 90         for(int i=0;i<k;i++){
 91             scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&g);
 92             int u=x1*maxn+y1,t=x2*maxn+y2;
 93             if(u>t)Swap(u,t);
 94             wall[u][t]=true;
 95             if(g){
 96                 d[g].push_back(door(u,t));
 97             }
 98         }
 99         scanf("%d",&s);
100         while(s--){
101             scanf("%d%d%d",&x1,&y1,&g);
102             int t=1<<(g-1);
103             for(int i=0;i<(1<<p);i++){
104                 if(i>(i^t))continue;
105                 add(i*maxn*maxn+x1*maxn+y1,(i^t)*maxn*maxn+x1*maxn+y1,0);
106             }
107         }
108         build();
109         printf("%d
",spfa());
110     }
111     return 0;
112 }