bzoj 5070 危险的迷宫

题目

bzoj5070
分析

相当于一个模板题
最小费用最大流，点权是费用，流量为1限制只能一个人走
考虑拆点，拆为入点与出点，建一个源点连起点，建一个汇点连终点
流量等于N就输出费用，小于N输出-1
题解：
代码

  1 /***************************
  2 User:Mandy.H.Y
  3 Language:c++
  4 Problem:maze
  5 Algorithm:
  6 Score:
  7 ***************************/
  8 
  9 //做网络流记得考虑拆点啊 
 10 
 11 #include<bits/stdc++.h>
 12 
 13 using namespace std;
 14 
 15 const int maxn = 150;
 16 const int maxint = 2100000000;
 17 
 18 int n,m,K,size=1,cur[4100],val[410],N,tot,s,t,cost,maxflow;
 19 //size从2开始 
 20 int first[410];
 21 bool vis[410];
 22 int dis[410];
 23 
 24 struct Edge{
 25     int v,nt,w,f;
 26 }edge[4100];
 27 
 28 char *TT,*mo,but[(1 << 15) + 2];
 29 #define getchar() ((TT == mo && (mo = ((TT = but) + fread(but,1,1 << 15,stdin)),TT == mo)) ? -1 : *TT++)
 30 template<class T>inline void read(T &x){
 31     x = 0;bool flag = 0;char ch = getchar();
 32     while(!isdigit(ch)) flag |= ch == '-',ch = getchar();
 33     while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48),ch = getchar();
 34     if(flag) x = -x;
 35 }
 36 
 37 template<class T>void putch(const T x){
 38     if(x > 9) putch(x / 10);
 39     putchar(x % 10 | 48);
 40 }
 41 
 42 template<class T>void put(const T x){
 43     if(x < 0) putchar('-'),putch(-x);
 44     else putch(x);
 45 }
 46 
 47 void file(){
 48     freopen("maze.in","r",stdin);
 49 //    freopen("maze.out","w",stdout);
 50 }
 51 
 52 void eadd(int u,int v,int w,int f){
 53     edge[++ size].v = v;edge[size].w = w;edge[size].f = f;edge[size].nt = first[u];first[u] = size;
 54     edge[++ size].v = u;edge[size].w = -w;edge[size].f = 0;edge[size].nt = first[v];first[v] = size;
 55 }
 56 
 57 void readdata(){
 58     read(n);read(m);
 59     tot = n*m;
 60     for(int i = 0;i < n; ++ i)
 61         for(int j = 0;j < m; ++ j){
 62             int id = i * m + j;
 63             read(val[id]);
 64             eadd(id,id + tot,val[id],1);
 65         }
 66     
 67     read(K);
 68     for(int i = 1;i <= K; ++ i){
 69         int u,v,x,y;
 70         read(u);read(v);read(x);read(y);
 71         eadd((u-1)*m+(v-1) + tot,(x-1)*m+(y-1),0,1);
 72         eadd((x-1)*m+(y-1) + tot,(u-1)*m+(v-1),0,1);
 73     }
 74     
 75     read(N);
 76     s = tot + tot + 1;
 77     t = tot + tot + 2;
 78     for(int i = 1;i <= N; ++ i){
 79         int x,y;
 80         read(x);read(y);
 81         eadd(s,(x-1)*m+(y-1),0,1);
 82     }
 83     for(int i = 1;i <= N; ++ i){
 84         int x,y;
 85         read(x);read(y);
 86         eadd((x-1)*m+(y-1)+tot,t,0,1);
 87     }
 88 } 
 89 
 90 bool SPFA(){
 91     memset(dis,0x3f3f3f3f,sizeof(dis));
 92     memset(vis,0,sizeof(vis));
 93     queue<int>q;
 94     dis[s] = 0;
 95     q.push(s);
 96     while(!q.empty()){
 97         int u = q.front();
 98         q.pop();
 99         vis[u] = 0;
100         for(int i = first[u];i;i = edge[i].nt){
101             int v = edge[i].v;
102             int w = edge[i].w;
103             if(dis[v] > dis[u] + w && edge[i].f){
104                 dis[v] = dis[u] + w;
105                 if(!vis[v]) q.push(v),vis[v] = 1;
106             }
107         }
108     }
109     return dis[t] != 0x3f3f3f3f;
110 }
111 
112 int dfs(int u,int flow){
113     if(u == t || flow == 0) return flow;
114     vis[u] = 1;
115     int left = flow;
116     
117     for(int i = first[u];i;i = edge[i].nt){
118         int v = edge[i].v;
119         if(edge[i].f && (!vis[v]) && dis[v] == dis[u] + edge[i].w){
120             
121             int maxf = dfs(v,min(left,edge[i].f));
122             edge[i].f -= maxf;
123             edge[i^1].f += maxf;
124             left -= maxf;
125             cost += edge[i].w * maxf;//要乘以流量 
126             
127             if(left <= 0){
128                 left = 0;
129                 break;
130             } 
131         }
132     }
133     
134     return flow - left;
135 }
136 
137 void work(){
138     
139     while(SPFA()){
140         maxflow += dfs(s,maxint);
141     }
142     if(maxflow == N) put(cost);
143     else puts("-1");
144 }
145 
146 int main(){
147 //    file();
148     readdata();
149     work();
150     return 0;
151 }
View Code
非做顽石不可，哪管他敬仰暗唾