做网站都要学什么,电脑自助建站,360浏览器怎么创建网页,网站模板 山先说PPT的思路
PPT的思路源于这句话#xff1a; 对每条边 (u, v)#xff0c;连一条 (u, v) 容量为 1#xff0c;费用为 1 的边。如果 流了表示删去这条边。
流过原图上的边表示删去这条边意味着什么呢#xff1f; 令dif[u]u的出度-入度 如图#xff0c;灰边表示原图上的…先说PPT的思路
PPT的思路源于这句话 对每条边 (u, v)连一条 (u, v) 容量为 1费用为 1 的边。如果 流了表示删去这条边。
流过原图上的边表示删去这条边意味着什么呢 令dif[u]u的出度-入度 如图灰边表示原图上的边初始状态没有流过任何边 因为原图没有边被删所以dif[u]-1
这时如果有一流量为1的流流过边a那么此流只能从u在原图上的出边流出即有一流量为1的流流过了边2代表原图中边2被删dif[u]dif[u]-1-2
因此s到u流一流量为Δx的流dif[u]要-Δx 同理如果有一流量为1的流流过边b那么此流只能从u在原图上的入边流入即有一流量为1的流流过了边1或边3代表原图中边1或边3被删dif[u]dif[u]10
因此u到t流一流量为Δx的流dif[u]要Δx
这样我们就将dif[u]值的变化量转化成了流过(s,u)边或(u,t)边的流量
如此限制入度与出度的差的绝对值的最大值就变得简单了 因此考虑二分答案
设v入度与出度的差的绝对值的最大值二分v然后求最少需要删去多少的边判断是否可行即可 在建图时
1.若dif[u]v:则dif[u]要减去一个数xx0,因为-vdif[u]-xv,所以dif[u]-vxdif[u]v,从s到u连一条上界为dif[u]v,下界为dif[u]-v,费用为0的边
2.若-vdif[u]v:从s到u连一条上界为dif[u]v,费用为0的边从u到t连一条上界为v-dif[u],费用为0的边
3.若dif[u]-v:从u到t连一条上界为v-dif[u],下界为-v-dif[u],费用为0的边跑有源汇有上下界的最小费用最大流即可
#includeiostream
#includecstdio
#includecstring
#includequeue
using namespace std;
const int N60;
const int M100005;
const int inf0x7fffffff;
struct Edge{int u,v,f,w,nxt;
}edge[M1];
int s,t,ss,tt,S,T,head[N],cnt,inque[N],pre[N],dis[N];
queueint que;
int Q,n,m,K,a[M],b[M],dif[N];
void add(int u,int v,int f,int w){edge[cnt].uu;edge[cnt].vv;edge[cnt].ww;edge[cnt].ff;edge[cnt].nxthead[u];head[u]cnt;edge[cnt].uv;edge[cnt].vu;edge[cnt].w-w;edge[cnt].f0;edge[cnt].nxthead[v];head[v]cnt;
}
bool spfa(){memset(dis,0x7f,sizeof(dis));memset(inque,0,sizeof(inque));memset(pre,-1,sizeof(pre));dis[S]0;que.push(S);inque[S]1;while(!que.empty()){int uque.front();que.pop();inque[u]0;for(int ihead[u];i!-1;iedge[i].nxt){int vedge[i].v;if(edge[i].f0dis[v]dis[u]edge[i].w){dis[v]dis[u]edge[i].w;pre[v]i;if(!inque[v]){que.push(v);inque[v]1;}}} }if(pre[T]-1) return 0;return 1;
}
int EK(){int flow,ret0;while(spfa()){flowinf;int xpre[T];while(x!-1){flowmin(edge[x].f,flow);xpre[edge[x].u];}xpre[T];while(x!-1){edge[x].f-flow;edge[x^1].fflow;retflow*edge[x].w;xpre[edge[x].u];}}return ret;
}
bool check(int v){cnt0;memset(head,-1,sizeof(head));sn1;tn2;ssn3;ttn4;add(t,s,inf,0);for(int i1;im;i)add(a[i],b[i],1,1);for(int i1;in;i){if(dif[i]v){add(s,i,2*v,0);add(ss,i,dif[i]-v,0);add(s,tt,dif[i]-v,0);//add(s,i,[dif[i]v,dif[i]-v],0);//减法上下界 }else if(dif[i]-v){add(s,i,dif[i]v,0);//减法上界 add(i,t,v-dif[i],0);//加法上界 }else{add(i,t,2*v,0);add(ss,t,-v-dif[i],0);add(i,tt,-v-dif[i],0);//add(i,t,[v-dif[i],-v-dif[i]],0);//加法上下界 }}Sss,Ttt;if(EK()K) return 1;return 0;
}
int main(){scanf(%d,Q);for(int cas1;casQ;cas){memset(dif,0,sizeof(dif));scanf(%d%d%d,n,m,K);Km-K;for(int i1;im;i){scanf(%d%d,a[i],b[i]);dif[b[i]]--;dif[a[i]];}int l0,rn,mid,ans;while(lr){mid(lr)/2;if(check(mid)){ansmid;rmid-1;}else lmid1;} printf(Case %d: %d\n,cas,ans);}return 0;
}接下来是我自己的思考产物还未验证
考虑如何转化 入度与出度之差。 设原图每条边流量为1入度与出度之差转化为一个点的流入量与流出量之差。 此时图是不满足流量平衡的所以对每个点我们给少的流一个来处多的流一个去处 入度与出度之差就转化为从来处到节点的流或从节点到去处的流的大小。
顺着想下去原图上的边有流流过就代表选择了这条边没有流流过就代表边被删除
考虑如何求解
原题最多k条边是限制入度与出度之差的绝对值的最大值最小是求最值 考虑二分答案入度与出度之差的绝对值变为限制用限制流量实现那么删去边数自然转为求的最值用费用求,与d比较判断即可
update: 我的思路会产生一个问题从源点到各节点的流的大小 代表 出度-入度 从各节点到汇点的流的大小 代表 入度-出度根据每个节点是出度大还是入度大我们选择连(s,u)还是(u,t)显然一个节点不能同时连两种边但因为题目限制的是 出度与入度之差的绝对值无论连哪种边其下界都会是负数目前我想到的唯一解决方法是将所有边的边界整体加上n
