首页 > 代码库 > 【网络流24题----14】孤岛营救问题
【网络流24题----14】孤岛营救问题
孤岛营救问题
Time Limit: 1 Sec Memory Limit: 128 MBDescription
1944年，特种兵麦克接到国防部的命令。要求马上赶赴太平洋上的一个孤岛，营救被敌军俘虏的大兵瑞恩。瑞恩被关押在一个迷宫里，迷宫地形复杂，但幸好麦克得到了迷宫的地形图。迷宫的外形是一个长方形，其南北方向被划分为 N行，东西方向被划分为 M列，于是整个迷宫被划分为 N×M个单元。每个单元的位置可用一个有序数对 (单元的行号，单元的列号)来表示。南北或东西方向相邻的 2个单元之间可能互通，也可能有一扇锁着的门。或者是一堵不可逾越的墙。
迷宫中有一些单元存放着钥匙，而且全部的门被分成 P类。打开同一类的门的钥匙同样，不同类门的钥匙不同。
大兵瑞恩被关押在迷宫的东南角。即(N，M)单元里，并已经昏迷。
迷宫仅仅有一个入口，在西北角。
也就是说，麦克能够直接进入(1，1)单元。
另外，麦克从一个单元移动到还有一个相邻单元的时间为 1。拿取所在单元的钥匙的时间以及用钥匙开门的时间可忽略不计。
试设计一个算法，帮助麦克以最快的方式到达瑞恩所在单元。营救大兵瑞恩。
Input
第 1行有 3个整数。分别表示 N,M,P的值。
第 2行是 1个整数 K，表示迷宫中门和墙的总数。
第 I+2行（1<=I<=K），有 5个整数。依次为 Xi1,Yi1,Xi2,Yi2,Gi：
当 Gi>=1时。表示(Xi1,Yi1)单元与(Xi2,Yi2)单元之间有一扇第 Gi类的门。
当 Gi=0时，表示(Xi1,Yi1)单元与(Xi2,Yi2)单元之间有一堵不可逾越的墙（当中，|Xi1-Xi2|+|Yi1-Yi2|=1， 0<=Gi<=P）。
第 K+3行是一个整数 S，表示迷宫中存放的钥匙总数。
第 K+3+J行(1<=J<=S)。有 3个整数，依次为 Xi1,Yi1,Qi：表示第 J把钥匙存放在(Xi1,Yi1)单元里，而且第 J把钥匙是用来开启第 Qi类门的。（当中 1<=Qi<=P）。
输入数据中同一行各相邻整数之间用一个空格分隔。
Output
输出麦克营救到大兵瑞恩的最短时间的值。假设问题无解，则输出-1。
Sample Input
Sample Output
HINT
N,M,P <= 10
K < 150
Source
网络流24题
分层图最短路属于网络流问题。。。。？！
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<vector> 5 #include<cstdlib> 6 #include<cmath> 7 #include<cstring> 8 using namespace std; 9 #define maxn 110 10 #define ZT ((1<<12)+1) 11 #define llg long long 12 #define maxlen 100000 13 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout); 14 #define inf (llg)1e16 15 llg n,m,to[5][2],dis[maxn][ZT],yaoshi[maxn],bj[maxn][ZT]; 16 llg p,k,S,head,tail; 17 18 llg num_(llg x,llg y){return (x-1)*m+y;} 19 20 struct node 21 { 22 llg p1,p2,ty; 23 }e[151]; 24 25 struct data 26 { 27 llg po,set; 28 }dl[maxlen+5]; 29 30 vector<llg>a[maxn]; 31 32 void init() 33 { 34 to[1][1]=1,to[2][1]=-1,to[3][0]=1,to[4][0]=-1; 35 cin>>n>>m>>p>>k; 36 p++; 37 llg x1,y1,x2,y2,z; 38 for (llg i=1;i<=k;i++) 39 { 40 scanf("%lld%lld%lld%lld%lld",&x1,&y1,&x2,&y2,&z); 41 llg x=num_(x1,y1); llg y=num_(x2,y2); 42 if (x>y) swap(x,y); 43 e[i].p1=x,e[i].p2=y,e[i].ty=z; 44 } 45 for (llg i=1;i<=n;i++) 46 for (llg j=1;j<=m;j++) 47 { 48 for (llg w=1;w<=4;w++) 49 if (i+to[w][0]>=1 && i+to[w][0]<=n && j+to[w][1]>=1 && j+to[w][1]<=m) 50 a[num_(i,j)].push_back(num_(i+to[w][0],j+to[w][1])); 51 } 52 cin>>S; 53 for (llg i=1;i<=S;i++) 54 { 55 scanf("%lld%lld%lld",&x1,&y1,&z); 56 yaoshi[num_(x1,y1)]|=(1<<z); 57 } 58 n*=m; 59 for (llg i=1;i<=n;i++) 60 for (llg j=0;j<(1<<p);j++) dis[i][j]=inf; 61 head=0,tail=1,dl[1].po=1,dl[1].set=0; 62 dis[1][0]=0; 63 } 64 65 llg find(llg x,llg y) 66 { 67 for (llg i=1;i<=k;i++) 68 if ((e[i].p1==x && e[i].p2==y) || (e[i].p1==y && e[i].p2==x)) return e[i].ty; 69 return -1; 70 } 71 72 void spfa() 73 { 74 llg x,v,se,w; 75 do 76 { 77 head%=maxlen; head++; 78 x=dl[head].po,se=dl[head].set,w=a[x].size(); 79 bj[x][se]=0; 80 for (llg i=0;i<w;i++) 81 { 82 v=a[x][i]; 83 llg color=find(x,v); 84 //if (color==0) continue; 85 if (yaoshi[x]!=0) 86 { 87 llg nse=se|yaoshi[x]; 88 if (dis[x][nse]>dis[x][se]) 89 { 90 dis[x][nse]=dis[x][se]; 91 if (!bj[x][nse]) 92 { 93 bj[x][nse]=1; 94 tail%=maxlen; 95 dl[++tail].po=x,dl[tail].set=nse; 96 } 97 } 98 } 99 100 if (color==0) continue;101 if (color>0)102 {103 if ((se&(1<<color))==0) continue;104 }105 if (dis[v][se]>dis[x][se]+1)106 {107 dis[v][se]=dis[x][se]+1;108 if (!bj[v][se])109 {110 bj[v][se]=1;111 tail%=maxlen; 112 dl[++tail].po=v,dl[tail].set=se;113 }114 }115 if (yaoshi[x]!=0)116 {117 llg nse=se|yaoshi[x];118 if (dis[v][nse]>dis[x][se]+1)119 {120 dis[v][nse]=dis[x][se]+1;121 if (!bj[v][nse])122 {123 bj[v][nse]=1;124 tail%=maxlen;125 dl[++tail].po=v,dl[tail].set=nse;126 }127 }128 }129 }130 }while (head!=tail);131 }132 133 int main()134 {135 yyj("save");136 init();137 spfa();138 llg ans=inf;139 for (llg i=0;i<(1<<p);i++) ans=min(ans,dis[n][i]);140 if (ans==inf) cout<<-1;else141 cout<<ans<<endl;142 return 0;143 }
【网络流24题----14】孤岛营救问题