hdu3987 最小割边数
题意：
是让你求最小割之后问最小割的最少边数是多少，因为最小割不是唯一的，所以存在最小边数的问法。
思路：
两个方法，一个是先一遍最大流，然后把割边全都改成流量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;
}
最新文章
- iOS之应用版本号的设置规则
- 浅谈WEB前后端分离
- Codeforces Round #384 (Div. 2) 734E Vladik and cards
- Js中强大的Promise异步机制
- Windows下打包Python的exe可执行文件
- Java Api与HBase交互实例
- Android 轻量级ORM数据库开源框架ActiveAndroid 源码分析
- 使用Android SDK Manager自动下载速度慢解决方法
- bzoj1379 [Baltic2001]Postman
- 如何用好 Google 搜索引擎？
- tee 命令详解
- php ueditor 后台配置项返回格式出错，上传功能将不能正常使用！
- Accesss数据库的DBhelper类（带分页）
- vue之简单组件例子
- mint修改host
- GitHub大佬：供计算机学习鉴黄功能的图片数据库
- ssh免密登录及去掉提示
- 学习ReentrantLock
- IAM：亚马逊访问权限控制
- pthreads v3下的worker和pool的使用