题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1001
题意：一个 n*m 的网格图，有斜边，边均有边权，切断边权和最小的边集使得无法从 (1,1) 到 (n,m)....
一眼最小割... 然而数据范围应该是过不去的... 敲了一发 dinic 试一试.. 然后就过了... 不知道是数据太水还是 dinic 的上界太松辣....
样例不过... 苦恼了一会发现是无项图... 所以连边直接双向都连边权即可...
正解太神，不会，先放着 orz
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 |
#include <cmath> #include <queue> #include <cstdio> #include <iomanip> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define inf 210000000 #define M 6000010 #define N 1000010 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } struct zgz { int next,to,val; }edge[M]; int cnt=2,head[M]; void add(int from,int to,int val) { edge[cnt].to=to; edge[cnt].val=val; edge[cnt].next=head[from]; head[from]=cnt++; } void insert(int from,int to,int val) {add(from,to,val);add(to,from,val);} int n,m,S,T,ans; int d[N]; queue<int> q; bool bfs() { memset(d,0,sizeof(d)); d[S]=1,q.push(S); while(!q.empty()) { int x=q.front();q.pop(); for(int i=head[x];i;i=edge[i].next) { int to=edge[i].to,val=edge[i].val; if(!d[to]&&val) { d[to]=d[x]+1; q.push(to); } } } if(d[T])return 1; return 0; } int dfs(int x,int v) { if(x==T||v==0)return v; int ret=0; for(int i=head[x];i;i=edge[i].next) { int to=edge[i].to,val=edge[i].val; if(d[to]==d[x]+1) { int f=dfs(to,min(v,val)); edge[i].val-=f,edge[i^1].val+=f; v-=f,ret+=f; if(v==0)break; } } if(ret==0)d[x]=-1; return ret; } int main() { n=read(),m=read();S=1,T=n*m; for(int i=1;i<=n;i++) for(int j=1;j<m;j++) { int tmp=read(); insert((i-1)*m+j,(i-1)*m+j+1,tmp); } for(int i=1;i<n;i++) for(int j=1;j<=m;j++) { int tmp=read(); insert((i-1)*m+j,i*m+j,tmp); } for(int i=1;i<n;i++) for(int j=1;j<m;j++) { int tmp=read(); insert((i-1)*m+j,i*m+j+1,tmp); } while(bfs())ans+=dfs(S,inf); printf("%d",ans); } |
Comments | NOTHING