网站建设投标方案,做网站虚拟主机好还是,怎样在浏览器上找网站,网站后台上传图片 不可用正题 题目大意
一个nnn行的不完全矩阵第iii行有mi−1mi-1mi−1个格子#xff0c;然后每个格子有危险度。 每次可以从(i,j)(i,j)(i,j)走到(i−1,j)(i-1,j)(i−1,j)或(i−1,j−1)(i-1,j-1)(i−1,j−1) 求
m次#xff0c;每个格子和路不可以重复走的最小危险度。m次#xff0…正题 题目大意
一个nnn行的不完全矩阵第iii行有mi−1mi-1mi−1个格子然后每个格子有危险度。 每次可以从(i,j)(i,j)(i,j)走到(i−1,j)(i-1,j)(i−1,j)或(i−1,j−1)(i-1,j-1)(i−1,j−1) 求
m次每个格子和路不可以重复走的最小危险度。m次路不可以重复但是格子可以的最小危险度。 解题思路
显然网络流把点拆开就可以限制重复走的。
然后第二问改一下就好了 codecodecode
#includecstdio
#includealgorithm
#includequeue
#includecstring
#define p(x,y,z) 2*((y-1)*nx)-z
using namespace std;
const int N200,inf2147483647/2;
struct node{int to,next,w,c;
}a[8*N*N];
int ans,n,m,s,e,tot1,dan[N][2*N],t;
int f[2*N*N],mf[2*N*N],ls[2*N*N],pre[2*N*N];
bool v[2*N*N];
queueint q;
void addl(int x,int y,int w,int c)
{a[tot].toy;a[tot].nextls[x];ls[x]tot;a[tot].ww;a[tot].cc;a[tot].tox;a[tot].nextls[y];ls[y]tot;a[tot].w0;a[tot].c-c;
}
bool spfa()
{memset(f,0x3f,sizeof(f));mf[s]inf;f[s]0;v[s]1;q.push(s);pre[e]0;while(!q.empty()){int xq.front();q.pop();v[x]0;for(int ils[x];i;ia[i].next){if(!a[i].w)continue;int ya[i].to;if(f[x]a[i].cf[y]){f[y]f[x]a[i].c;mf[y]min(a[i].w,mf[x]);pre[y]i;if(!v[y]){q.push(y);v[y]1;}}}}return pre[e];
}
void over_path()
{int nowe,w0,flowmf[e];ansmf[e]*f[e];while(now!s){a[pre[now]].w-flow;a[pre[now]^1].wflow;nowa[pre[now]^1].to;}
}
void Net_flow()
{while(spfa())over_path();
}
int main()
{scanf(%d%d,n,m);e0;sp(n,nm-1,1)1;ts1;for(int i1;in;i)for(int j1;jmi-1;j){scanf(%d,dan[i][j]);if(i1)addl(p(i,j,1),t,inf,0);if(in)addl(s,p(i,j,0),inf,0);addl(p(i,j,0),p(i,j,1),1,dan[i][j]);if(jmi-1i1) addl(p(i,j,1),p(i-1,j,0),1,0);if(j1i1) addl(p(i,j,1),p(i-1,j-1,0),1,0);}addl(t,e,m,0);Net_flow();printf(%d\n,ans);ans0;tot1;memset(ls,0,sizeof(ls));for(int i1;in;i)for(int j1;jmi-1;j){if(i1)addl(p(i,j,1),t,m,0);if(in)addl(s,p(i,j,0),m,0);addl(p(i,j,0),p(i,j,1),m,dan[i][j]);if(jmi-1i1) addl(p(i,j,1),p(i-1,j,0),1,0);if(j1i1) addl(p(i,j,1),p(i-1,j-1,0),1,0);}addl(t,e,m,0);Net_flow();printf(%d,ans);
}
