南约社区网站建设,网站开发建设方案,百度电商平台app,广东网站建设电话咨询题目#xff1a;https://loj.ac/problem/2979 原来的思路#xff1a; 优化连边。一看就是同一个桌子相邻座位之间连边、相邻桌子对应座位之间连边。 每个座位向它所属的桌子连边。然后每个人建一个点#xff0c;向若干桌子连边。 因为连边的桌子是区间#xff0c;所以线段树…题目https://loj.ac/problem/2979 原来的思路 优化连边。一看就是同一个桌子相邻座位之间连边、相邻桌子对应座位之间连边。 每个座位向它所属的桌子连边。然后每个人建一个点向若干桌子连边。 因为连边的桌子是区间所以线段树优化。 又想到志愿者招募之类的所以想弄一个上下界费用流。人向它的座位连下界为1的边对应桌子区间向人连边。找一些循环流。 #includecstdio
#includecstring
#includealgorithm
#includequeue
#define ls Ls[cr]
#define rs Rs[cr]
using namespace std;
int rdn()
{int ret0;bool fx1;char chgetchar();while(ch9||ch0){if(ch-)fx0;chgetchar();}while(ch0ch9)retret*10ch-0,chgetchar();return fx?ret:-ret;
}
int Mn(int a,int b){return ab?a:b;}
const int N305,M15,N27000,M2140000,INF3005;
int n,m,S,T,L[N][M],R[N][M],dy[N],bh[N][M],tot,Ls[N1],Rs[N1];
int rd[N2],hd[N2],xnt1,to[M2],nxt[M2],cap[M2],w[M2];
int ans,dis[N2],pr[N2],info[N2]; bool ins[N2];
queueint q;
void add(int x,int y,int l,int r,int z)
{rd[y]l; rd[x]-l; ansl*z; r-l;to[xnt]y;nxt[xnt]hd[x];hd[x]xnt;cap[xnt]r;w[xnt]z;to[xnt]x;nxt[xnt]hd[y];hd[y]xnt;cap[xnt]0;w[xnt]-z;
}
void build(int l,int r,int cr)
{if(lr){dy[l]cr;return;}int midlr1;lstot; build(l,mid,ls);rstot; build(mid1,r,rs);add(ls,cr,0,INF,0); add(rs,cr,0,INF,0);
}
void qry(int l,int r,int cr,int L,int R,int k)
{if(lLrR){printf((%d-%d)\n,cr,k);add(cr,k,0,1,0);return;}int midlr1;if(Lmid)qry(l,mid,ls,L,R,k);if(midR)qry(mid1,r,rs,L,R,k);
}
bool spfa()
{memset(dis,0x3f,sizeof dis); info[T]0;dis[S]0; info[S]INF; q.push(S); ins[S]1;while(q.size()){int kq.front(); q.pop(); ins[k]0;for(int ihd[k],v;i;inxt[i])if(cap[i]dis[vto[i]]dis[k]w[i]){dis[v]dis[k]w[i];pr[v]i; info[v]Mn(info[k],cap[i]);if(!ins[v])ins[v]1,q.push(v);}}return info[T];
}
int ek()
{int tpinfo[T];for(int ipr[T];i;ipr[to[i^1]]){cap[i]-tp; cap[i^1]tp;answ[i]*tp;printf(%d ,to[i]);}puts();return tp;
}
int main()
{nrdn();mrdn();for(int i1;in;i)for(int j1;jm;j)L[i][j]rdn()1;//1for(int i1;in;i)for(int j1;jm;j)R[i][j]rdn()1;tot1;build(1,n,1); int tmpn*m;for(int i1;in;i,puts())for(int j1;jm;j)bh[i][j]tot,printf(%d ,tot);for(int i1;in;i)for(int j1;jm;j){qry(1,n,1,L[i][j],R[i][j],bh[i][j]tmp);printf((%d-%d)\n,bh[i][j]tmp,bh[i][j]);add(bh[i][j]tmp,bh[i][j],1,1,0);printf((%d-%d)\n,bh[i][j],dy[i]);add(bh[i][j],dy[i],1,1,0);printf((%d-%d)[]\n,bh[i][j],bh[i][jm?1:j1]);add(bh[i][j],bh[i][jm?1:j1],0,INF,1);printf((%d-%d)[]\n,bh[i][j],bh[i][j1?j-1:m]);add(bh[i][j],bh[i][j1?j-1:m],0,INF,1);if(in){printf((%d-%d)[]\n,bh[i][j],bh[i1][j]);add(bh[i][j],bh[i1][j],0,INF,2);}}tottmp; Stot1; Ttot2; tmp0;printf(S%d T%d\n,S,T);for(int i1;itot;i)if(rd[i]0)add(i,T,0,-rd[i],0);else if(rd[i]0)add(S,i,0,rd[i],0),tmprd[i];printf(tmp%d ans%d\n,tmp,ans);while(spfa())tmp-ek();if(tmp)puts(no solution);else printf(%d\n,ans);return 0;
} View Code 然后发现过不了样例。这样是不行的。希望的是 “因为自己连向 x 座位、 y 桌子向自己连边所以 x 座位到 y 桌子走了一条路” 但实际上这样相当于自己给 x 座位一些流量、自己向 y 桌子索求一些流量如果有另一个人给 y 桌子某座位一些流量、向 x 座位所在桌子索求流量那么 x 和 y 之间本应有两条路现在一条也没有了。 正解和这个类似 每种座位都建两棵线段树维护所有桌子一棵表示向左走一棵表示向右走即一共 2*m 棵线段树。 然后每个人向线段树对应节点连边线段树叶子就表示座位同一个桌子的座位之间连边即可。 向左走的线段树从自己到左孩子连的边费用需要加上 “跨过右孩子” 的代价。即到达向左走的线段树某节点默认当前在该区间的右端点。所以每个人向区间连的 log 条边要注意一下初始费用。 需要多路增广费用流才能过。多路增广就是 spfa 一次之后根据 dis[ cr ] 和 dis[ v ] 的关系像 dinic 一样走。 dinic 的优化都可以加似乎一定要加当前弧优化注意要像 dfs 一样打 vis 标记因为 dis 上可能有 0 环。 #includecstdio
#includecstring
#includealgorithm
#includequeue
#define ls Ls[cr]
#define rs Rs[cr]
using namespace std;
int rdn()
{int ret0;bool fx1;char chgetchar();while(ch9||ch0){if(ch-)fx0;chgetchar();}while(ch0ch9)retret*10ch-0,chgetchar();return fx?ret:-ret;
}
int Mn(int a,int b){return ab?a:b;}
int Mx(int a,int b){return ab?a:b;}
const int N18005,M276005,INF3005;
int n,m,S,T,L[305][15],R[305][15],bh[305][15];
int tot,Ls[N],Rs[N],hd[N],xnt1,to[M],nxt[M],cap[M],w[M];
int ans,mxflow,dis[N],pr[N],info[N]; bool ins[N];
int cur[N];bool vis[N];
queueint q;
void add(int x,int y,int c,int z)
{to[xnt]y;nxt[xnt]hd[x];hd[x]xnt;cap[xnt]c;w[xnt]z;to[xnt]x;nxt[xnt]hd[y];hd[y]xnt;cap[xnt]0;w[xnt]-z;
}
void build(int l,int r,int cr,bool fx,int k)
{if(lr){if(!fx)bh[l][k]tot;add(cr,bh[l][k],INF,0); return;}int midlr1;lstot; build(l,mid,ls,fx,k);rstot; build(mid1,r,rs,fx,k);if(fx){ add(cr,ls,INF,0); add(cr,rs,INF,(mid-l1)*2);}else{ add(cr,ls,INF,(r-mid)*2); add(cr,rs,INF,0);}
}
void qry(int l,int r,int cr,int L,int R,int lj,bool fx)
{if(lLrR){ add(tot,cr,1,lj);return;}int midlr1;if(!fx){if(Lmid)qry(l,mid,ls,L,R,lj2*(r-mid),fx);if(midR)qry(mid1,r,rs,L,R,lj,fx);}else{if(Lmid)qry(l,mid,ls,L,R,lj,fx);if(midR)qry(mid1,r,rs,L,R,lj2*(mid-l1),fx);}
}
bool spfa()
{memset(dis,0x3f,sizeof dis); info[T]0;dis[S]0; info[S]INF; q.push(S); ins[S]1;while(q.size()){int kq.front(); q.pop(); ins[k]0;for(int ihd[k],v;i;inxt[i])if(cap[i]dis[vto[i]]dis[k]w[i]){dis[v]dis[k]w[i];pr[v]i; info[v]Mn(info[k],cap[i]);if(!ins[v])ins[v]1,q.push(v);}}return info[T];
}
int dfs(int cr,int flow)
{if(crT)return flow;int use0; vis[cr]1;for(int icur[cr],v;i;inxt[i])if(cap[i]!vis[vto[i]]dis[v]dis[cr]w[i]){int tmpdfs(v,Mn(flow-use,cap[i]));if(!tmp)dis[v]-1;cap[i]-tmp; cap[i^1]tmp; anstmp*w[i];usetmp; if(useflow){vis[cr]0;return use;}}vis[cr]0; return use;
}
void solve()
{int tmp;while(spfa()){memcpy(cur,hd,sizeof hd);while(tmpdfs(S,INF))mxflowtmp;}
}
int main()
{nrdn();mrdn();for(int i1;in;i)for(int j1;jm;j) L[i][j]rdn()1;//1for(int i1;in;i)for(int j1;jm;j) R[i][j]rdn()1;tot2*m;for(int i1;im;i){ build(1,n,i,0,i); build(1,n,im,1,i);}for(int i1;in;i)for(int j1;jm;j){ add(bh[i][j],bh[i][jm?1:j1],INF,1);add(bh[i][j],bh[i][j1?m:j-1],INF,1);}for(int i1;in;i)for(int j1;jm;j){tot;if(L[i][j]i)qry(1,n,j,L[i][j],Mn(i-1,R[i][j]),-2*(n-i),0);if(R[i][j]i)qry(1,n,jm,Mx(L[i][j],i),R[i][j],-2*(i-1),1);}Stot1; Ttot2;for(int itot-n*m1;itot;i)add(S,i,1,0);for(int i1;in;i)for(int j1;jm;j)add(bh[i][j],T,1,0);solve();if(mxflown*m)puts(no solution);else printf(%d\n,ans);return 0;
} 转载于:https://www.cnblogs.com/Narh/p/10841141.html
