POJ1325二分匹配或者DINIC(最小路径覆盖)

题意：

有k个任务，两个机器，第一个机器有n个模式，第二个机器有m个模式，每个任务要么在第一个机器的一个模式下工作，要么在第二个机器的一个模式下工作，机器每切换一个模式需要重启一次，两个机器一开始都处于第0个模式下，问完成这k个任务至少切换多少次模式（任务完成顺序无所谓）。

思路：

把每个任务的两个点连成一条边，然后就是说每个边肯定要先则这条边的两个端点中的一个，所有的边都要这样做，这不就是最少顶点覆盖了吗，直接一遍二分匹配就行了，或者是一遍最大流，线面是两种方法的代码，题目比较简单，就说这么多吧。

二分匹配，匈牙利（最少顶点覆盖=最大匹配数）

#include<stdio.h>

#include<string.h>

#define N_node 200 + 10

#define N_edge 1000 + 100

typedef struct

{

int to ,next;

}STAR;

STAR E[N_edge];

int list[N_node] ,tot;

int mkdfs[N_node] ,mkgx[N_node];

void add(int a ,int b)

{

E[++tot].to = b;

E[tot].next = list[a];

list[a] = tot;

}

int DFS_XYL(int s)

{

for(int k = list[s] ;k ;k = E[k].next)

{

int to = E[k].to;

if(mkdfs[to]) continue;

mkdfs[to] = 1;

if(mkgx[to] == -1 || DFS_XYL(mkgx[to]))

{

mkgx[to] = s;

return 1;

}

}

return 0;

}

int main ()

{

int n ,m, k ,a ,b ,c ,i;

while(~scanf("%d" ,&n) && n)

{

scanf("%d %d" ,&m ,&k);

memset(list ,0 ,sizeof(list));

tot = 1;

for(i = 1 ;i <= k ;i ++)

{

scanf("%d %d %d" ,&a ,&b ,&c);

if(!b || !c) continue;

add(b + 1 ,c + 1);

}

memset(mkgx ,255 ,sizeof(mkgx));

int Ans = 0;

for(i = 1 ;i <= n ;i ++)

{

memset(mkdfs ,0 ,sizeof(mkdfs));

Ans += DFS_XYL(i);

}

printf("%d\n" ,Ans);

}

return 0;

}

DINIC求最大匹配

#include<queue>

#include<stdio.h>

#include<string.h>

#define N_node 250

#define N_edge 3000

#define INF 1000000000

using namespace std;

typedef struct

{

int to ,next ,cost;

}STAR;

typedef struct

{

int x ,t;

}DEP;

STAR E[N_edge];

DEP xin ,tou;

int list[N_node] ,listt[N_node] ,tot;

int deep[N_node];

void add(int a ,int b ,int c)

{

E[++tot].to = b;

E[tot].cost = c;

E[tot].next = list[a];

list[a] = tot;

E[++tot].to = a;

E[tot].cost = 0;

E[tot].next = list[b];

list[b] = tot;

}

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 ++)

listt[i] = list[i];

return deep[t] != -1;

}

int minn(int x ,int y)

{

return x < y ? x : y;

}

int DFS_Flow(int s ,int t ,int flow)

{

if(s == t) return flow;

int nowflow = 0;

for(int k = listt[s] ;k ;k = E[k].next)

{

int to = E[k].to;

int c = E[k].cost;

listt[s] = k;

if(deep[to] != deep[s] + 1 || !c)

continue;

int 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;

}

int DINIC(int s ,int t ,int n)

{

int Ans = 0;

while(BFS_Deep(s ,t ,n))

{

Ans += DFS_Flow(s ,t ,INF);

}

return Ans;

}

int main ()

{

int n ,m ,k ,i ,a ,b ,c;

while(~scanf("%d" ,&n) && n)

{

scanf("%d %d" ,&m ,&k);

memset(list ,0 ,sizeof(list));

tot = 1;

for(i = 1 ;i <= k ;i ++)

{

scanf("%d %d %d" ,&a ,&b ,&c);

if(!b || !c) continue;

b ++ ,c ++;

add(b ,c + n ,1);

}

for(i = 1 ;i <= n ;i ++)

add(0 ,i ,1);

for(i = 1 ;i <= m ;i ++)

add(i + n ,n + m + 1 ,1);

printf("%d\n" ,DINIC(0 ,m + n + 1 ,m + n + 1));

}

return 0;

}

巴特西

POJ1325二分匹配或者DINIC(最小路径覆盖)

最新文章

热门文章