fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8. #define fi first
  9. #define se second
  10. #define mp make_pair
  11. #define pb push_back
  12. #define fbo find_by_order
  13. #define ook order_of_key
  14.  
  15. typedef long long ll;
  16. typedef pair<ll,ll> ii;
  17. typedef vector<int> vi;
  18. typedef long double ld; 
  19. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
  20. typedef set<int>::iterator sit;
  21. typedef vector<int>::iterator vit;
  22.  
  23. struct Edge{
  24.     int u, v;
  25.     long long cap, cost;
  26.  
  27.     Edge(int _u, int _v, long long _cap, long long _cost){
  28.         u = _u; v = _v; cap = _cap; cost = _cost;
  29.     }
  30. };
  31.  
  32. const ll INF = ll(1e9);
  33. struct MinCostFlow{
  34.     int n, s, t;
  35.     long long flow, cost;
  36.     vector<vector<int> > graph;
  37.     vector<Edge> e;
  38.     vector<bool> me;
  39.     vector<long long> dist, potential;
  40.     vector<int> parent;
  41.     bool negativeCost;
  42.  
  43.     MinCostFlow(int _n){
  44.         // 0-based indexing
  45.         me.assign(_n, 0);
  46.         n = _n;
  47.         graph.assign(n, vector<int> ());
  48.         negativeCost = false;
  49.     }
  50.  
  51.     void addEdge(int u, int v, long long cap, long long cost, bool directed = true){
  52.         if(cost < 0)
  53.             negativeCost = true;
  54.  
  55.         graph[u].push_back(e.size());
  56.         e.push_back(Edge(u, v, cap, cost));
  57.  
  58.         graph[v].push_back(e.size());
  59.         e.push_back(Edge(v, u, 0, -cost));
  60.         if(!directed)
  61.             addEdge(v, u, cap, cost, true);
  62.     }
  63.  
  64.     pair<long long, long long> getMinCostFlow(int _s, int _t){
  65.         s = _s; t = _t;
  66.         flow = 0, cost = 0;
  67.  
  68.         potential.assign(n, 0);
  69.         if(negativeCost){
  70.             // run Bellman-Ford to find starting potential
  71.             dist.assign(n, 1LL<<62);
  72.             for(int i = 0, relax = false; i < n && relax; i++, relax = false){
  73.                 for(int u = 0; u < n; u++){
  74.                     for(int k = 0; k < graph[u].size(); k++){
  75.                         int eIdx = graph[u][i];
  76.                         int v = e[eIdx].v, cap = e[eIdx].cap, w = e[eIdx].cost;
  77.  
  78.                         if(dist[v] > dist[u] + w && cap > 0){
  79.                             dist[v] = dist[u] + w;
  80.                             relax = true;
  81.             }   }   }   }
  82.  
  83.             for(int i = 0; i < n; i++){
  84.                 if(dist[i] < (1LL<<62)){
  85.                     potential[i] = dist[i];
  86.         }   }   }
  87.  
  88.         while(dijkstra()){
  89.             flow += sendFlow(t, 1LL<<62);
  90.         }
  91.  
  92.         return make_pair(flow, cost);
  93.     }
  94.  
  95.     bool dijkstra(){
  96.         parent.assign(n, -1);
  97.         dist.assign(n, 1LL<<62);
  98.         priority_queue<ii, vector<ii>, greater<ii> > pq;
  99.  
  100.         dist[s] = 0;
  101.         pq.push(ii(0, s));
  102.  
  103.  
  104.         while(!pq.empty()){
  105.             int u = pq.top().second;
  106.             long long d = pq.top().first;
  107.             pq.pop();
  108.  
  109.             if(d != dist[u]) continue;
  110.  
  111.             for(int i = 0; i < graph[u].size(); i++){
  112.                 int eIdx = graph[u][i];
  113.                 int v = e[eIdx].v, cap = e[eIdx].cap;
  114.                 int w = e[eIdx].cost + potential[u] - potential[v];
  115.  
  116.                 if(dist[u] + w < dist[v] && cap > 0){
  117.                     dist[v] = dist[u] + w;
  118.                     parent[v] = eIdx;
  119.  
  120.                     pq.push(ii(dist[v], v));
  121.         }   }   }
  122.  
  123.         // update potential
  124.         for(int i = 0; i < n; i++)
  125.         {
  126.             if(dist[i] < (1LL<<62))
  127.                 potential[i] += dist[i];
  128.         }
  129.  
  130.         return dist[t] != (1LL<<62);
  131.     }
  132.  
  133. 	void dfs(int s)
  134. 	{
  135. 		me[s]=1;
  136. 		//cerr<<s<<'\n';
  137. 		for(int i = 0; i < graph[s].size(); i++)
  138. 		{
  139. 			 int eIdx = graph[s][i];
  140.              int v = e[eIdx].v; ll cap = e[eIdx].cap;
  141.              if(cap==0) continue;
  142.              if(!me[v])
  143.              {
  144. 				 dfs(v);
  145. 			 }
  146. 		}
  147. 	}
  148.     long long sendFlow(int v, long long curFlow){
  149.         if(parent[v] == -1)
  150.             return curFlow;
  151.         int eIdx = parent[v];
  152.         int u = e[eIdx].u, w = e[eIdx].cost;
  153.  
  154.         long long f = sendFlow(u, min(curFlow, e[eIdx].cap));
  155.  
  156.         cost += f*w;
  157.         e[eIdx].cap -= f;
  158.         e[eIdx^1].cap += f;
  159.  
  160.         return f;
  161.     }
  162. };
  163.  
  164. int n, m;
  165. int dx[4] = {1, -1, 0, 0};
  166. int dy[4] = {0, 0, 1, -1};
  167.  
  168. int inid(int x, int y)
  169. {
  170. 	return 2*(x*m+y);
  171. }
  172.  
  173. int outid(int x, int y)
  174. {
  175. 	return 2*(x*m+y)+1;
  176. }
  177.  
  178. MinCostFlow mcmf(5111);
  179.  
  180. bool isvalid(int x, int y)
  181. {
  182. 	if(x>=0&&x<n&&y>=0&&y<m) return 1;
  183. 	return 0;
  184. }
  185. int E[51][51];
  186. bool good[51][51];
  187.  
  188. int main()
  189. {
  190. 	ios_base::sync_with_stdio(0); cin.tie(0);
  191. 	int X, Y;
  192. 	cin>>n>>m>>X>>Y;
  193. 	int s = 2*m*n; int e = 2*m*n+1;
  194. 	for(int i = 0; i < n; i++)
  195. 	{
  196. 		for(int j = 0; j < m; j++)
  197. 		{
  198. 			ll p; cin >> p;
  199. 			if(X-1==i&&Y-1==j) p = INF;
  200. 			//cerr<<"SQUARE : "<<inid(i,j)<<' '<<outid(i,j)<<' '<<p<<'\n';
  201. 			E[i][j] = mcmf.e.size();
  202. 			mcmf.addEdge(inid(i,j),outid(i,j),p,0);
  203. 			if(p==INF)
  204. 			{
  205. 				mcmf.addEdge(outid(i,j),e,INF,0);
  206. 			}
  207. 		}
  208. 	}
  209. 	for(int i = 0; i < n; i++)
  210. 	{
  211. 		for(int j = 0; j < m; j++)
  212. 		{
  213. 			for(int k = 0; k < 4; k++)
  214. 			{
  215. 				int x = i+dx[k]; int y = j+dy[k];
  216. 				if(isvalid(x, y))
  217. 				{
  218. 					//cerr<<i<<' '<<j<<' '<<x<<' '<<y<<'\n';
  219. 					if(X-1==x&&Y-1==y)
  220. 					{
  221. 						mcmf.addEdge(outid(i,j),inid(x,y),INF,0);
  222. 					}
  223. 					else
  224. 					{
  225. 						mcmf.addEdge(outid(i,j),inid(x,y),INF,0);
  226. 					}
  227. 				}
  228. 			}
  229. 			if(i==0||i==n-1||j==0||j==m-1)
  230. 			{
  231. 				mcmf.addEdge(s, inid(i, j),INF,0);
  232. 			}
  233. 		}
  234. 	}
  235. 	ii tmp = mcmf.getMinCostFlow(s, e);
  236. 	cout << tmp.fi << '\n';
  237. 	mcmf.dfs(s);
  238. 	for(int i = 0; i < n; i++)
  239. 	{
  240. 		for(int j = 0; j < m; j++)
  241. 		{
  242. 			if((mcmf.me[inid(i,j)]^mcmf.me[outid(i,j)]))
  243. 			{
  244. 				cout<<'X';
  245. 			}
  246. 			else
  247. 			{
  248. 				cout<<'.';
  249. 			}
  250. 		}
  251. 		cout<<'\n';
  252. 	}
  253. }
Success #stdin #stdout 0s 3672KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/IU0MIi
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!