因为某个地方m写成n玄学调bug一个小时...
写完内心是崩溃的...
#include<iostream> #include<cstdio> #include<cstring> #include <list> #include <algorithm> #include <vector> #include <queue> #define N 40010 #define inf 1000000000 using namespace std; class Graphic{ public: friend void show(); void init(int a,int b){ src = a,dst = b; if(dst >= N)for(;;); for(int i = 0 ; i <= dst ; ++i)G[i].clear(); edge.clear(); cnt = 0; } void add(int u,int v,int cap){ _add(u,v,cap); _add(v,u,0); } int Dinic(){ int ans = 0; while (bfs()) { memset(cur, 0, sizeof(cur)); ans+=dfs(src,inf); } return ans; } private: bool bfs(){ while (!que.empty())que.pop(); que.push(src); memset(dis,-1, sizeof(dis)); dis[src] = 0; while(!que.empty()){ int u = que.front(); que.pop(); for(int i = 0 ; i < G[u].size() ; ++i){ int v = edge[G[u][i]].to; if(edge[G[u][i]].cap and dis[v]==-1){ dis[v] = dis[u]+1; que.push(v); } } } return dis[dst]!=-1; } int dfs(int u,int a){ if(u==dst or a == 0)return a; int ret = 0,f; for(int &i = cur[u] ; i < G[u].size() ; ++i){ int v = edge[G[u][i]].to; int tmp = edge[G[u][i]].cap; if(dis[v] == dis[u] + 1 and tmp > 0 and (f = dfs(v,min(a,tmp)))>0){ ret+=f; edge[G[u][i]].cap-=f; edge[G[u][i]^1].cap+=f; a-=f; if(a==0)break; } } return ret; } private: int src,dst,dis[N],cur[N]; int cnt; struct Edge{ int to,cap; Edge(int a,int b):to(a),cap(b){} }; queue<int>que; vector<int>G[N]; vector<Edge>edge; void _add(int u,int v,int d){ edge.emplace_back(Edge(v,d)); G[u].push_back(cnt++); } }; Graphic ss; char str[105][105][10]; int down_right[105][105][2],n,m; int get_dat(char *s){ int ans = 0; while (*s and isdigit(*s)){ ans = ans*10+*s-'0'; ++s; } return ans; } int id[105][105],tol; void deal(int i,int j){ int cnt; down_right[i][j][0] = isdigit(str[i][j][0])?get_dat(str[i][j]):-1; down_right[i][j][1] = isdigit(str[i][j][4])?get_dat(str[i][j]+4):-1; if(isdigit(str[i][j][0])){ cnt = 0; for(int k = i+1 ; k <= n and str[k][j][0]=='.' ; ++k){ ++cnt; } down_right[i][j][0]-=cnt; } if(isdigit(str[i][j][4])){ cnt = 0; for(int k = j+1 ; k <= m and str[i][k][0]=='.' ; ++k){ ++cnt; } down_right[i][j][1]-=cnt; } if(isdigit(str[i][j][0])or isdigit(str[i][j][4])){ id[i][j]=++tol; ++tol; } } int res[105][105]; void show(){ for(int i = 1 ; i <= n ; ++i){ for(int j = 1 ; j <= m/**因为这里笔者调了一个小时....**/ ; ++j){ if(down_right[i][j][1]!=-1){ for(int k = 1 ; str[i][j+k][0]=='.' and k < ss.G[id[i][j]+1].size() ; ++k){ /// cerr<<ss.edge[ss.G[id[i][j]+1][k]].to<<" "<<id[i][j]+1<<endl; res[i][j+k] = 9 - ss.edge[ss.G[id[i][j]+1][k]].cap; } } } } for(int i = 1 ; i <= n ; ++i){ for(int j = 1 ; j <= m ; ++j){ if(str[i][j][0]=='.'){ printf("%d",res[i][j]); ///if(res[i][j]==0x3f3f3f3f)for(;;); } else putchar('_'); putchar(j==m?' ':' '); } puts(""); } } int main(){ while(cin>>n>>m){ for(int i = 1 ; i <= n ; ++i){ for(int j = 1 ; j <= m ; ++j){ scanf("%s",str[i][j]); } } int num = 0; tol = 0; for(int i = 1 ; i <= n ; ++i){ for(int j = 1 ; j <= m ; ++j){ deal(i,j); } } int src = 0,dst = tol+1; ss.init(src,dst); for(int i = 1 ; i <= n ; ++i){ for(int j = 1 ; j <= m ; ++j){ if(down_right[i][j][1]!=-1){ /// cerr<<i<<" "<<j<<":"; ss.add(src,id[i][j]+1,down_right[i][j][1]); for(int k = j+1 ; k <= m and str[i][k][0]=='.' ; ++k){ int to = i-1; for( ; to > 1 and str[to][k][0]=='.'; --to); if(down_right[to][k][0]==-1)for(;;); ss.add(id[i][j]+1,id[to][k],8); } } if(down_right[i][j][0]!=-1){ ss.add(id[i][j],dst,down_right[i][j][0]); } } } ss.Dinic(); show(); } } /** 2 4 xxxxxxx 002/xxx xxxxxxx 002/xxx xxx/002 ....... xxx/002 ....... */
一个模板可以用一年..
从题目抽象出网络流的概念，从源点向横向格子建边，横向格子向对应竖向建边，竖向格子向汇点建边，跑网络流无脑找出流量即可。