hdu3987 最小割边数
最小
2023-09-11 14:14:00 时间
题意:
是让你求最小割之后问最小割的最少边数是多少,因为最小割不是唯一的,所以存在最小边数的问法。
思路:
两个方法,一个是先一遍最大流,然后把割边全都改成流量1,其他的全都改成流量无穷就行了,第二个方法是比较经典的方法,就是把权值放大 *(E+1)+1,最后在对(E+1)取余就行了,这么干其实是同时跑了两遍最大流,只不过是两个权值之间的差距太大,不会相互影响。
#include<queue>
#include<stdio.h>
#include<string.h>
#define N_node 1000 + 5
#define N_edge 400000 + 100
#define INF 2055000000
using namespace std;
typedef struct
{
int from ,to ,next;
long long cost;
}STAR;
typedef struct
{
int x ,t;
}DEP;
STAR E[N_edge];
DEP xin ,tou;
int list[N_node] ,list2[N_node] ,tot;
int deep[N_node];
void add(int a ,int b ,long long c)
{
E[++tot].from = a;
E[tot].to = b;
E[tot].cost = c;
E[tot].next = list[a];
list[a] = tot;
E[++tot].from = b;
E[tot].to = a;
E[tot].cost = 0;
E[tot].next = list[b];
list[b] = tot;
}
long long minn(long long a ,long long b)
{
return a < b ? a : b;
}
bool BFS_Deep(int s ,int t ,int n)
{
memset(deep ,255 ,sizeof(deep));
xin.x = s ,xin.t = 0;
deep[s] = 0;
queue<DEP>q;
q.push(xin);
while(!q.empty())
{
tou = q.front();
q.pop();
for(int k = list[tou.x] ;k ;k = E[k].next)
{
xin.x = E[k].to;
xin.t = tou.t + 1;
if(deep[xin.x] != -1 || !E[k].cost)
continue;
deep[xin.x] = xin.t;
q.push(xin);
}
}
for(int i = 0 ;i <= n ;i ++)
list2[i] = list[i];
return deep[t] != -1;
}
long long DFS_Flow(int s ,int t ,long long flow)
{
if(s == t) return flow;
long long nowflow = 0;
for(int k = list2[s] ;k ;k = E[k].next)
{
list2[s] = k;
int to = E[k].to;
long long c = E[k].cost;
if(deep[to] != deep[s] + 1 || !c) continue;
long long tmp = DFS_Flow(to ,t ,minn(c ,flow - nowflow));
nowflow += tmp;
E[k].cost -= tmp;
E[k^1].cost += tmp;
if(nowflow == flow) break;
}
if(!nowflow) deep[s] = 0;
return nowflow;
}
long long Ans = 0;
while(BFS_Deep(s ,t ,n))
{
Ans += DFS_Flow(s ,t ,INF);
}
return Ans;
}
int main ()
{
int a ,b ,c ,d;
int t ,n ,m ,i ,cas = 1;
scanf("%d" ,&t);
while(t--)
{
scanf("%d %d" ,&n ,&m);
memset(list ,0 ,sizeof(list));
tot = 1;
for(i = 1 ;i <= m ;i ++)
{
scanf("%d %d %d %d" ,&a ,&b ,&c ,&d);
if(d) add(a + 1 ,b + 1 ,(long long)c) ,add(b + 1 ,a + 1 ,c);
else add(a + 1 ,b + 1 ,(long long)c);
}
DINIC(1 ,n ,n);
for(i = 2 ;i <= tot ;i += 2)
if(!E[i].cost) E[i].cost = 1 ,E[i^1].cost = 0;
else E[i].cost = INF ,E[i^1].cost = 0;
printf("Case %d: %lld\n" ,cas ++ ,DINIC(1 ,n ,n));
}
return 0;
}
#include<queue>
#include<stdio.h>
#include<string.h>
#define N_node 1000 + 5
#define N_edge 400000 + 100
#define INF 205500000000000//这个地方记得开大点,因为放大了权值
using namespace std;
typedef struct
{
int from ,to ,next;
long long cost;
}STAR;
typedef struct
{
int x ,t;
}DEP;
STAR E[N_edge];
DEP xin ,tou;
int list[N_node] ,list2[N_node] ,tot;
int deep[N_node];
void add(int a ,int b ,long long c)
{
E[++tot].from = a;
E[tot].to = b;
E[tot].cost = c;
E[tot].next = list[a];
list[a] = tot;
E[tot].cost = 0;
E[tot].next = list[b];
list[b] = tot;
}
long long minn(long long a ,long long b)
{
return a < b ? a : b;
}
bool BFS_Deep(int s ,int t ,int n)
{
memset(deep ,255 ,sizeof(deep));
xin.x = s ,xin.t = 0;
deep[s] = 0;
queue<DEP>q;
q.push(xin);
while(!q.empty())
{
tou = q.front();
q.pop();
for(int k = list[tou.x] ;k ;k = E[k].next)
{
xin.x = E[k].to;
xin.t = tou.t + 1;
if(deep[xin.x] != -1 || !E[k].cost)
continue;
deep[xin.x] = xin.t;
q.push(xin);
}
}
for(int i = 0 ;i <= n ;i ++)
list2[i] = list[i];
return deep[t] != -1;
}
long long DFS_Flow(int s ,int t ,long long flow)
{
if(s == t) return flow;
long long nowflow = 0;
for(int k = list2[s] ;k ;k = E[k].next)
{
list2[s] = k;
int to = E[k].to;
long long c = E[k].cost;
if(deep[to] != deep[s] + 1 || !c) continue;
long long tmp = DFS_Flow(to ,t ,minn(c ,flow - nowflow));
nowflow += tmp;
E[k].cost -= tmp;
E[k^1].cost += tmp;
if(nowflow == flow) break;
}
if(!nowflow) deep[s] = 0;
return nowflow;
}
long long DINIC(int s ,int t ,int n)
{
long long Ans = 0;
while(BFS_Deep(s ,t ,n))
{
Ans += DFS_Flow(s ,t ,INF);
}
return Ans;
}
int main ()
{
int a ,b ,c ,d;
int t ,n ,m ,i ,cas = 1;
scanf("%d" ,&t);
while(t--)
{
scanf("%d %d" ,&n ,&m);
memset(list ,0 ,sizeof(list));
tot = 1;
for(i = 1 ;i <= m ;i ++)
{
scanf("%d %d %d %d" ,&a ,&b ,&c ,&d);
if(d) add(a + 1 ,b + 1 ,(long long)c * 100001 + 1) ,add(b + 1 ,a + 1 ,(long long)c * 100001 + 1);
else add(a + 1 ,b + 1 ,(long long)c * 100001 + 1);
}
printf("Case %d: %lld\n" ,cas ++ ,DINIC(1 ,n ,n) % 100001);
}
return 0;
}
是让你求最小割之后问最小割的最少边数是多少,因为最小割不是唯一的,所以存在最小边数的问法。
思路:
两个方法,一个是先一遍最大流,然后把割边全都改成流量1,其他的全都改成流量无穷就行了,第二个方法是比较经典的方法,就是把权值放大 *(E+1)+1,最后在对(E+1)取余就行了,这么干其实是同时跑了两遍最大流,只不过是两个权值之间的差距太大,不会相互影响。
#include<queue>
#include<stdio.h>
#include<string.h>
#define N_node 1000 + 5
#define N_edge 400000 + 100
#define INF 2055000000
using namespace std;
typedef struct
{
int from ,to ,next;
long long cost;
}STAR;
typedef struct
{
int x ,t;
}DEP;
STAR E[N_edge];
DEP xin ,tou;
int list[N_node] ,list2[N_node] ,tot;
int deep[N_node];
void add(int a ,int b ,long long c)
{
E[++tot].from = a;
E[tot].to = b;
E[tot].cost = c;
E[tot].next = list[a];
list[a] = tot;
E[++tot].from = b;
E[tot].to = a;
E[tot].cost = 0;
E[tot].next = list[b];
list[b] = tot;
}
long long minn(long long a ,long long b)
{
return a < b ? a : b;
}
bool BFS_Deep(int s ,int t ,int n)
{
memset(deep ,255 ,sizeof(deep));
xin.x = s ,xin.t = 0;
deep[s] = 0;
queue<DEP>q;
q.push(xin);
while(!q.empty())
{
tou = q.front();
q.pop();
for(int k = list[tou.x] ;k ;k = E[k].next)
{
xin.x = E[k].to;
xin.t = tou.t + 1;
if(deep[xin.x] != -1 || !E[k].cost)
continue;
deep[xin.x] = xin.t;
q.push(xin);
}
}
for(int i = 0 ;i <= n ;i ++)
list2[i] = list[i];
return deep[t] != -1;
}
long long DFS_Flow(int s ,int t ,long long flow)
{
if(s == t) return flow;
long long nowflow = 0;
for(int k = list2[s] ;k ;k = E[k].next)
{
list2[s] = k;
int to = E[k].to;
long long c = E[k].cost;
if(deep[to] != deep[s] + 1 || !c) continue;
long long tmp = DFS_Flow(to ,t ,minn(c ,flow - nowflow));
nowflow += tmp;
E[k].cost -= tmp;
E[k^1].cost += tmp;
if(nowflow == flow) break;
}
if(!nowflow) deep[s] = 0;
return nowflow;
}
long long DINIC(int s ,int t ,int n)
{long long Ans = 0;
while(BFS_Deep(s ,t ,n))
{
Ans += DFS_Flow(s ,t ,INF);
}
return Ans;
}
int main ()
{
int a ,b ,c ,d;
int t ,n ,m ,i ,cas = 1;
scanf("%d" ,&t);
while(t--)
{
scanf("%d %d" ,&n ,&m);
memset(list ,0 ,sizeof(list));
tot = 1;
for(i = 1 ;i <= m ;i ++)
{
scanf("%d %d %d %d" ,&a ,&b ,&c ,&d);
if(d) add(a + 1 ,b + 1 ,(long long)c) ,add(b + 1 ,a + 1 ,c);
else add(a + 1 ,b + 1 ,(long long)c);
}
DINIC(1 ,n ,n);
for(i = 2 ;i <= tot ;i += 2)
if(!E[i].cost) E[i].cost = 1 ,E[i^1].cost = 0;
else E[i].cost = INF ,E[i^1].cost = 0;
printf("Case %d: %lld\n" ,cas ++ ,DINIC(1 ,n ,n));
}
return 0;
}
#include<queue>
#include<stdio.h>
#include<string.h>
#define N_node 1000 + 5
#define N_edge 400000 + 100
#define INF 205500000000000//这个地方记得开大点,因为放大了权值
using namespace std;
typedef struct
{
int from ,to ,next;
long long cost;
}STAR;
typedef struct
{
int x ,t;
}DEP;
STAR E[N_edge];
DEP xin ,tou;
int list[N_node] ,list2[N_node] ,tot;
int deep[N_node];
void add(int a ,int b ,long long c)
{
E[++tot].from = a;
E[tot].to = b;
E[tot].cost = c;
E[tot].next = list[a];
list[a] = tot;
E[++tot].from = b;
E[tot].to = a;E[tot].cost = 0;
E[tot].next = list[b];
list[b] = tot;
}
long long minn(long long a ,long long b)
{
return a < b ? a : b;
}
bool BFS_Deep(int s ,int t ,int n)
{
memset(deep ,255 ,sizeof(deep));
xin.x = s ,xin.t = 0;
deep[s] = 0;
queue<DEP>q;
q.push(xin);
while(!q.empty())
{
tou = q.front();
q.pop();
for(int k = list[tou.x] ;k ;k = E[k].next)
{
xin.x = E[k].to;
xin.t = tou.t + 1;
if(deep[xin.x] != -1 || !E[k].cost)
continue;
deep[xin.x] = xin.t;
q.push(xin);
}
}
for(int i = 0 ;i <= n ;i ++)
list2[i] = list[i];
return deep[t] != -1;
}
long long DFS_Flow(int s ,int t ,long long flow)
{
if(s == t) return flow;
long long nowflow = 0;
for(int k = list2[s] ;k ;k = E[k].next)
{
list2[s] = k;
int to = E[k].to;
long long c = E[k].cost;
if(deep[to] != deep[s] + 1 || !c) continue;
long long tmp = DFS_Flow(to ,t ,minn(c ,flow - nowflow));
nowflow += tmp;
E[k].cost -= tmp;
E[k^1].cost += tmp;
if(nowflow == flow) break;
}
if(!nowflow) deep[s] = 0;
return nowflow;
}
long long DINIC(int s ,int t ,int n)
{
long long Ans = 0;
while(BFS_Deep(s ,t ,n))
{
Ans += DFS_Flow(s ,t ,INF);
}
return Ans;
}
int main ()
{
int a ,b ,c ,d;
int t ,n ,m ,i ,cas = 1;
scanf("%d" ,&t);
while(t--)
{
scanf("%d %d" ,&n ,&m);
memset(list ,0 ,sizeof(list));
tot = 1;
for(i = 1 ;i <= m ;i ++)
{
scanf("%d %d %d %d" ,&a ,&b ,&c ,&d);
if(d) add(a + 1 ,b + 1 ,(long long)c * 100001 + 1) ,add(b + 1 ,a + 1 ,(long long)c * 100001 + 1);
else add(a + 1 ,b + 1 ,(long long)c * 100001 + 1);
}
printf("Case %d: %lld\n" ,cas ++ ,DINIC(1 ,n ,n) % 100001);
}
return 0;
}
相关文章
- UVA11384正整数序列(把123..变成0的最小步数)
- 【华为OD机试真题 python】等和子数组最小和【2022 Q4 | 100分】
- BZOJ1185 : [HNOI2007]最小矩形覆盖
- 魔术索引(返回索引值最小的一个)
- 【BZOJ2597】[Wc2007]剪刀石头布 最小费用流
- 用不到 50 行的 Python 代码构建最小的区块链
- Excel—分组然后取每组中对应时间列值最大的或者最小的
- 最小生成树之Prime法
- 洛谷 P3366 【模板】最小生成树
- 华为OD机试 - 最小传递延迟(Java) | 机试题+算法思路+考点+代码解析 【2023】
- poj 1789 Truck History (最小生成树)
- Python实现基于最小二乘法的线性回归
- [LeetCode] 235. Lowest Common Ancestor of a Binary Search Tree 二叉搜索树的最小共同父节点
- 最小二乘法求回归直线方程的推导过程
- leetcode 64. Minimum Path Sum 最小路径和(中等)