[luoguP2764] 最小路径覆盖问题(最大流 || 二分图最大匹配)
2024-08-30 01:52:30
可惜洛谷上没有special judge,不然用匈牙利也可以过的,因为匈牙利在增广上有一个顺序问题,所以没有special judge就过不了了。
好在这个题的测试数据比较特殊,如果是网络流的话按照顺序加边,就可以过。
最小不相交路径覆盖 = 总点数 - 最大匹配数
——代码
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#define N 20001
#define min(x, y) ((x) < (y) ? (x) : (y))
#define max(x, y) ((x) > (y) ? (x) : (y)) int n, m, cnt, sum, s, t;
int head[N], belong[N], to[N], next[N], val[N], suc[N], cur[N], dis[N]; inline int read()
{
int x = , f = ;
char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -;
for(; isdigit(ch); ch = getchar()) x = (x << ) + (x << ) + ch - '';
return x * f;
} inline void add(int x, int y, int z)
{
to[cnt] = y;
val[cnt] = z;
next[cnt] = head[x];
head[x] = cnt++;
} inline bool bfs()
{
int i, u, v;
std::queue <int> q;
memset(dis, -, sizeof(dis));
q.push(s);
dis[s] = ;
while(!q.empty())
{
u = q.front(), q.pop();
for(i = head[u]; i ^ -; i = next[i])
{
v = to[i];
if(val[i] && dis[v] == -)
{
dis[v] = dis[u] + ;
if(v == t) return ;
q.push(v);
}
}
}
return ;
} inline int dfs(int u, int maxflow)
{
if(u == t) return maxflow;
int i, v, d, ret = ;
for(i = cur[u]; i ^ -; i = next[i])
{
v = to[i];
if(val[i] && dis[v] == dis[u] + )
{
d = dfs(v, min(val[i], maxflow - ret));
ret += d;
cur[u] = i;
val[i] -= d;
val[i ^ ] += d;
if(d) suc[u] = v - n;
if(ret == maxflow) return ret;
}
}
return ret;
} int main()
{
int i, j, x, y, now;
n = read();
m = read();
s = , t = (n << ) + ;
memset(head, -, sizeof(head));
for(i = ; i <= m; i++)
{
x = read();
y = read();
add(x, y + n, );
add(y + n, x, );
}
for(i = ; i <= n; i++)
{
add(s, i, );
add(i, s, );
add(i + n, t, );
add(t, i + n, );
}
while(bfs())
{
for(i = s; i <= t; i++) cur[i] = head[i];
sum += dfs(s, 1e9);
}
for(i = ; i <= n; i++)
if(suc[i])
{
now = i;
while(now)
{
printf("%d ", now);
x = suc[now];
suc[now] = ;
now = x;
}
puts("");
}
printf("%d\n", n - sum);
return ;
}
最新文章
- 纯js实现复制到剪贴板功能
- PDF.NET SOD 开源框架红包派送活动 &;&; 新手快速入门指引
- [转]NullPointerException异常
- 9.19 JS数组
- Ubuntu 开机进入命令行模式
- Unity3D独立游戏开发日记(二):摆放建筑物
- 某些输入文件使用或覆盖了已过时的 API
- Query for Component Path within PeopleSoft Portal
- iPhone开发 Swift - NSNotification 通知
- compile php 5.4
- 【转】cocos2d-x 开发中使用的一些工具
- java.util.Dictionary源码分析
- 解密电子书之二:EPD控制芯片
- iOS 关于js与OC相互调用的那些事
- vijos 1213:80人环游世界
- python之闭包与装饰器
- 使用foreach需要判空。
- Redis基础入门
- 使用阿里云OSS,上传图片时报错:java.lang.ClassNotFoundException:org.apache.http.ssl.TrustStrategy
- [转] 2016 JavaScript 发展现状大调查