20230812
P2764 最小路径覆盖问题
题目描述
传送门
给定一张DAG，要求用最少的路径覆盖整张图。数据范围：\(n, m \le 100\)。
Solution
经典问题
考虑把每一个点拆成两个点：入点和出点
对于每一条边 \(u \to v\) ，我们把 \(u\) 的出点与 \(v\) 的入点相连
再把 \(st\) 与所有点的出点相连，\(ed\) 与所有点的入点相连
这样跑一遍最大流 \(dinic()\)，答案就是 \(n-flow\)
#include <bits/stdc++.h>
using namespace std;
const int N=6e3+5,inf=0x3f3f3f3f;
int n,m,head[N],tot=0,ans=0,lv[N],st,ed,cur[N],fa[N],cnt=0,vis[N];
struct edge{
int u,v,nxt,val;
}e[N<<1];
int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
void add(int u,int v){
e[++tot]=(edge){u,v,head[u],1};
head[u]=tot;
e[++tot]=(edge){v,u,head[v],0};
head[v]=tot;
}
bool bfs(){
for(int i=0;i<=n*2+1;i++) lv[i]=-1;
queue<int> q;
q.push(st);
lv[st]=1;
cur[st]=head[st];
while(!q.empty()){
int u=q.front();q.pop();
for(int i=head[u];i!=-1;i=e[i].nxt){
int v=e[i].v,val=e[i].val;
if(val>0&&lv[v]==-1){
q.push(v);;
cur[v]=head[v];
lv[v]=lv[u]+1;
}
}
}
return lv[ed]!=-1;
}
int dfs(int u,int flow){
if(u==ed) return flow;
int res=flow;
for(int i=cur[u];i!=-1;i=e[i].nxt){
cur[u]=i;
int v=e[i].v,val=e[i].val;
if(lv[v]==lv[u]+1&&val>0){
int c=dfs(v,min(val,res));
res-=c;
e[i].val-=c;
e[i^1].val+=c;
}
}
return flow-res;
}
int dinic(){
int res=0;
while(bfs()) res+=dfs(st,inf);
return res;
}
int find(int x){
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
void marge(int u,int v){
u=find(u);v=find(v);
if(u!=v) fa[u]=v;
}
vector<vector<int> > g(N);
void work(){
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=0,u,v;i<=tot;i+=2){
if(e[i].val==1||e[i].u==st||e[i].v==ed) continue;
u=e[i].u;v=e[i].v;
if(u>n) u-=n;
if(v>n) v-=n;
marge(u,v);
}
cnt=0;
for(int i=1;i<=n;i++){
if(!vis[find(i)]) vis[fa[i]]=++cnt;
g[vis[fa[i]]].push_back(i);
}
for(int i=1;i<=cnt;i++){
for(int j=0;j<g[i].size();j++)
printf("%d ",g[i][j]);
printf("\n");
}
}
int main(){
/*2023.8.19 H_W_Y P2764 最小路径覆盖问题 网络最大流*/
n=read();m=read();
st=0;ed=n*2+1;
memset(head,-1,sizeof(head));tot=-1;
for(int i=1;i<=n;i++) add(st,i),add(i+n,ed);
for(int i=1,u,v;i<=m;i++){
u=read();v=read();
add(u,v+n);
}
ans=n-dinic();
work();
printf("%d\n",ans);
return 0;
}
P3254 圆桌问题
题目描述
传送门
有来自 \(m\) 个不同单位的代表参加一次国际会议。
第 \(i\) 个单位派出了 \(r_i\) 个代表。 会议的餐厅共有 \(n\) 张餐桌，第 \(i\) 张餐桌可容纳 \(c_i\) 个代表就餐。
为了使代表们充分交流，希望从同一个单位来的代表不在同一个餐桌就餐。
请给出一个满足要求的代表就餐方案。
\(1 \le m \le 150，1 \le n \le 270，1 \le r_i, c_i \le 10^3\)。
Solution
简单易懂
建立一个二分图，左部点是单位，右部点是餐桌。
从 \(s\) 向每个单位连一条容量为 \(r_i\) 的边，表示代表个数的限制。
从每个单位向每个餐桌连一条容量为 \(1\) 的边，表示每个餐桌相同单位至多一个人。
从每个餐桌向 \(t\) 连一条容量为 \(c_i\) 的边，表示一个餐桌最多坐 \(c_i\) 个人。
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e3+10,INF=0x3f3f3f3f;
int n,m,a[maxn],head[maxn],tot=-1,cur[maxn],lv[maxn],s,t,sum=0;
struct edge{
int u,v,nxt,val;
}e[maxn*maxn];
void add(int u,int v,int val){
e[++tot]=(edge){u,v,head[u],val};
head[u]=tot;
e[++tot]=(edge){v,u,head[v],0};
head[v]=tot;
}
bool bfs(){
memset(lv,-1,sizeof(lv));
queue<int> q;
q.push(s);
cur[s]=head[s];
lv[s]=1;
while(!q.empty()){
int now=q.front();q.pop();
for(int i=head[now];i!=-1;i=e[i].nxt){
int v=e[i].v,val=e[i].val;
if(lv[v]==-1&&val>0){
q.push(v);
cur[v]=head[v];
lv[v]=lv[now]+1;
}
}
}
return lv[t]!=-1;
}
int dfs(int now,int flow){
if(now==t) return flow;
int res=flow;
for(int i=cur[now];i!=-1;i=e[i].nxt){
cur[now]=i;
int v=e[i].v,val=e[i].val;
if(val>0&&lv[v]==lv[now]+1){
int c=dfs(v,min(res,val));
res-=c;
e[i].val-=c;
e[i^1].val+=c;
}
}
return flow-res;
}
int dinic(){
int ans=0;
while(bfs()) ans+=dfs(0,INF);
return ans;
}
int main(){
/*2023.2.25 hewanying P3254 [网络流24题]圆桌问题 网络最大流*/
scanf("%d%d",&m,&n);
s=0,t=n+m+2;
memset(head,-1,sizeof(head));
for(int i=1;i<=m;i++){
scanf("%d",&a[i]);
add(s,i,a[i]);
sum+=a[i];
}
for(int i=m+1;i<=n+m;i++){
scanf("%d",&a[i]);
add(i,t,a[i]);
for(int j=1;j<=m;j++) add(j,i,1);
}
if(dinic()==sum){
printf("1\n");
for(int i=1;i<=m;i++){
for(int j=head[i];j!=-1;j=e[j].nxt)
if(!(j&1)&&e[j].val==0) printf("%d ",e[j].v-m);
printf("\n");
}
}
else printf("0\n");
return 0;
}
P2472 [SCOI2007] 蜥蜴
题目描述
传送门
一个 \(n \times m\) 的网格中，有一些格子有石柱，石柱的高度为 \(1 \sim 3\)。
有一些石柱的顶上有蜥蜴，蜥蜴每次可以跳到距离不超过 \(d\) 的石柱上，或者跳到界外。
蜥蜴跳一次， 它所在的石柱的高度就减一，如果某个石柱的高度为 \(0\) 了，石柱就消失，以后蜥蜴不能跳到这里。现在要使得剩下无法逃脱的蜥蜴数最少。
\(1 \le r, c \le 20, 1 \le d \le 4\)。
Solution
简单易懂
将每个石柱拆成两个点，之间连容量为高度 \(h\) 的边，表示对经过这个石柱的蜥蜴数量限制。
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e3+10,INF=0x3f3f3f3f;
int n,m,d,lv[maxn],s,t,head[maxn],tot=-1,x,cur[maxn],a[maxn][maxn],sum=0;
string st;
struct edge{
int u,v,nxt,val;
}e[maxn*maxn];
void add(int u,int v,int val){
e[++tot]=(edge){u,v,head[u],val};
head[u]=tot;
e[++tot]=(edge){v,u,head[v],0};
head[v]=tot;
}
bool bfs(){
memset(lv,-1,sizeof(lv));
lv[s]=0;cur[s]=head[s];
queue<int> q;
q.push(s);
while(!q.empty()){
int now=q.front();q.pop();
for(int i=head[now];i!=-1;i=e[i].nxt){
int v=e[i].v,val=e[i].val;
if(val>0&&lv[v]==-1){
lv[v]=lv[now]+1;
cur[v]=head[v];
q.push(v);
}
}
}
return lv[t]!=-1;
}
int dfs(int now,int flow){
if(now==t) return flow;
int res=flow;
for(int i=cur[now];i!=-1;i=e[i].nxt) {
cur[now]=i;
int v=e[i].v,val=e[i].val;
if(val>0&&lv[v]==lv[now]+1){
int c=dfs(v,min(res,val));
res-=c;
e[i].val-=c;
e[i^1].val+=c;
}
}
return flow-res;
}
int dinic(){
int ans=0;
while(bfs()) ans+=dfs(s,INF);
return ans;
}
int main(){
/*2023.3.4 hewanying P2472 蜥蜴 网络最大流*/
memset(head,-1,sizeof(head));tot=-1;
scanf("%d%d%d",&n,&m,&d);
s=0;t=2*n*m+1;
for(int i=1;i<=n;i++){
cin>>st;
for(int j=1;j<=m;j++){
a[i][j]=x=st[j-1]-'0';
if(x==0) continue;
add(2*(n*(i-1)+j)-1,2*(n*(i-1)+j),x);
if(i<=d||n-i<d||j<=d||m-j<d) add(2*(n*(i-1)+j),t,INF);
for(int k=1;k<=i;k++)
for(int k2=1;k2<=m;k2++){
if(k==i&&k2==j) break;
if((k-i)*(k-i)+(j-k2)*(j-k2)<=d*d&&a[k][k2]>0){
add(2*(n*(k-1)+k2),2*(n*(i-1)+j)-1,INF);
add(2*(n*(i-1)+j),2*(n*(k-1)+k2)-1,INF);
}
}
}
}
for(int i=1;i<=n;i++){
cin>>st;
for(int j=0;j<m;j++)
if(st[j]=='L') sum++,add(s,2*(n*(i-1)+j+1)-1,1);
}
printf("%d\n",sum-dinic());
return 0;
}