P14122 [SCCPC 2021] Direction Setting
题目链接
题目大意
给定一个有n个结点,m条边的无向图,要求给每一条边加上方向,使之变为一个有向图,并使$ D=\sum_{i=0}^{n}max(0,di-ai) $的值最小,其中$ai$是第i个点的限度,$di$是第i个点的入度。
前置知识
最小费用流
分析
对D进行分析可以看出,当$di<=ai$时,顶点i对答案无贡献,否则对答案有$di-ai$的贡献。转换一下,就是每个点都会产生一定的代价,并且每条边都只能指向一个方向,具有流量限度,因此我们可以联想到网络流中的最小费用流。
构图
整个网络流可以分为3层:
第一层:源点→边节点
S → 边i : 容量1, 费用0
含义:每条边提供1个入度资源
第二层:边界点→顶点节点
边i → 顶点u : 容量1, 费用0
边i → 顶点v : 容量1, 费用0
含义:边i可以选择给u或v增加入度
第三层:顶点节点 → 汇点
顶点i → T : 容量a[i], 费用0
顶点i → T : 容量∞, 费用1
含义:前a[i]个入度免费,超出部分每个代价
第一层,源点S中存储整个图的入度总和,因为共有m条边,所以源点的值为m。从S到原图中每一条边都构建一条边,容量为1,费用为0,表示每条边能提供1个入度。第二层,由于原图中的每个边都只能有一个方向,因此让原图中的边向顶点构建容量为1的边,哪条边流满了就代表这条边指向谁。第三层,最关键的一层。每个顶点要向汇点建2条边,因为当$di<=ai$时,顶点i不会产生代价,因此建立一条容量为$ai$,费用为0的边,表示前$ai$个边都是免费的。当$di>ai$时,会产生$di-ai$的代价,由于最后一定会到达汇点,所以容量设为∞,费用为1,流过多少水流就会产生多少代价。
剩下的就是最小费用最大流模板了,可以用SPFA+单路增广来做,具体做法在此不多赘述。
求方向
遍历原图中的每一条边,对于每一条边节点,它在网络流中一定指向两个点节点,只需要看哪个边的容量为0即可,因为每个边节点只提供一个入度,所以流满的那条就是原图中边的方向。
其余细节见代码注释
code
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll N=1010,inf=1e9+7;
ll n,m,_;
ll a[N],ans[N];
ll S,T,mcost;
struct node{ll to,val,cost,nxt;
}e[N*10];
ll h[N],tot;
struct edge{ll u,v;
}s[N];
void add(ll u,ll v,ll w,ll c){e[++tot].to=v;e[tot].val=w;e[tot].cost=c;e[tot].nxt=h[u];h[u]=tot;return;
}
void init(){memset(h,0,sizeof(h));memset(ans,0,sizeof(ans));scanf("%lld%lld",&n,&m);T=m+n+1;tot=1;mcost=0;for(ll i=1;i<=n;i++) scanf("%lld",&a[i]);//存下来原图中的信息 for(ll i=1;i<=m;i++) scanf("%lld%lld",&s[i].u,&s[i].v);/*网络流中各个编号节点所对应的信息:0:源点 1~m:原图中的每一条边m+1~m+n:原图中的每一个点m+n+1:汇点 *///第一层 for(ll i=1;i<=m;i++){add(S,i,1,0);add(i,S,0,0);}//第二层 ll u,v;for(ll i=1;i<=m;i++){u=s[i].u;v=s[i].v;add(i,m+u,1,0);add(m+u,i,0,0);add(i,m+v,1,0);add(m+v,i,0,0);}//第三层 for(ll i=1;i<=n;i++){add(m+i,T,a[i],0);add(T,m+i,0,0);add(m+i,T,inf,1);add(T,m+i,0,-1);}return;
}
bool vis[N<<1];
ll pre[N<<1],pedge[N<<1],dis[N<<1];
//pre[i]:存储网络流中到达节点i的前驱节点
//pedge[i]:存储从pre[i]到i的边的编号
bool spfa(){for(ll i=0;i<=T;i++) dis[i]=inf;memset(vis,0,sizeof(vis));queue<ll> q;q.push(S);dis[S]=0;vis[S]=1;ll u,v,w,c;while(q.size()){u=q.front();q.pop();vis[u]=0;for(ll i=h[u];i;i=e[i].nxt){v=e[i].to;w=e[i].val;c=e[i].cost;if(w<=0) continue;if(dis[v]>dis[u]+c){dis[v]=dis[u]+c;pre[v]=u;pedge[v]=i;if(!vis[v]){q.push(v);vis[v]=1;}}}}if(dis[T]==inf) return 0;return 1;
}
void mcmf(){ll now,t;//最小费用流模板 while(spfa()){now=inf;for(ll i=T;i!=S;i=pre[i])now=min(now,e[pedge[i]].val);for(ll i=T;i!=S;i=pre[i]){//增广路 t=pedge[i];e[t].val-=now;e[t^1].val+=now;mcost+=now*e[t].cost;}}printf("%lld\n",mcost);//输出方向 ll u,v,w;for(ll i=1;i<=m;i++){u=s[i].u;for(ll j=h[i];j;j=e[j].nxt){v=e[j].to;w=e[j].val;//网络流中节点m+u就是原图中的节点u if(v==m+u&&w==0){//正向(u→v)时为0,所以只需要判断边是否反向(u←v) ans[i]=1;break;}}}for(ll i=1;i<=m;i++) printf("%lld",ans[i]);putchar('\n');return;
}
int main(){scanf("%lld",&_);while(_--){init();mcmf();}return 0;
}