最大流的应用,最小路径覆盖,地址: http://acm.pku.edu.cn/JudgeOnline/problem?id=1422
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) /**//*距离标号的最大流*/
#include <stdio.h>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int LEN = 500;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int MAX = 0x7fffffff;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
struct
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int c;
int f;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) }map[LEN][LEN]; /**//*邻接矩阵*/
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
struct
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int node;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) }nearl[LEN][LEN];/**//*邻接链表,第一个表示最后一个位置*/
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void initm ( int n )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
for ( int i=0; i<n; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
nearl[i][0].node = 0;
for ( int j=0; j<n; j++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
map[i][j].c = map[i][j].f = 0;
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int dis[LEN];//标号的数组
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void initd ( int n )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
for ( int i=0; i<n; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
dis[i] = -1;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int que[LEN];
int head, tail;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void initq ()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
head = 0;
tail = -1;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void inq ( int in )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
que[++tail] = in;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void outq ( int *out )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
*out = que[head++];
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int testempty ()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
return head > tail ? 1 : 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int mark ( int s, int t, int n )/**//*进行距离标号*/
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int out;
int in;
initd ( n );
initq ();
inq ( s );
dis[s] = 0;
while ( ! testempty () )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
outq ( &out );
if ( out == t )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
return 1;
}
for ( int p=1; p<=nearl[out][0].node; p++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
in = nearl[out][p].node;
if ( map[out][in].c > map[out][in].f || map[in][out].f > 0 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if ( dis[in] == -1 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
dis[in] = dis[out] + 1;
inq ( in );
}
}
}
}
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
typedef struct
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int now;
int from;
int weight;
}type;
type stack[LEN];//用于记录路径的堆栈
int top;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void inits ()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
top = -1;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void push ( type *in )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
top ++;
stack[top].now = in->now;
stack[top].from = in->from;
stack[top].weight = in->weight;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void pop ()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
top --;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int gettop ()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
return stack[top].now;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int minest ( int a, int b )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
return a < b ? a : b;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int ad ()/**//*流量调整函数*/
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int now, from;
int min = MAX;
int i;
for ( i=1; i<=top; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
now = stack[i].now;
from = stack[i].from;
if ( stack[i].weight > 0 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
min = minest ( min, map[from][now].c-map[from][now].f );
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
min = minest ( min, map[now][from].f );
}
}
for ( i=1; i<=top; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
now = stack[i].now;
from = stack[i].from;
if ( stack[i].weight > 0 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
map[from][now].f += min;
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
map[now][from].f -= min;
}
}
return min;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int maxflow ( int s, int t, int n )/**//*最小费用最大流函数*/
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int p;
int i;
int flow = 0;
type in;
while ( mark ( s, t, n ) )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
inits ();
in.now = s;
in.from = -1;
in.weight = 1;
push ( &in );
while ( ( p = gettop () ) != t )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
for ( i=1; i<=nearl[p][0].node; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
int v = nearl[p][i].node;
if ( map[p][v].c > map[p][v].f )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if ( dis[p] == dis[v] - 1 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
in.now = v;
in.from = p;
in.weight = 1;
push ( &in );
break;
}
}
if ( map[v][p].f > 0 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if ( dis[p] == dis[v] - 1 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
in.now = v;
in.from = p;
in.weight = -1;
push ( &in );
break;
}
}
}
if ( i > nearl[p][0].node )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
dis[p] = n;
pop ();
}
}
flow += ad ();
}
return flow;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void add ( int a, int b, int c )//增加一条边
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
if ( ! map[a][b].c && ! map[b][a].c )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
int p = nearl[a][0].node;
nearl[a][++p].node = b;
nearl[a][0].node ++;
p = nearl[b][0].node;
nearl[b][++p].node = a;
nearl[b][0].node ++;
}
map[a][b].c += c;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main ()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int t, n, m;
int b, e;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
while ( scanf ( "%d", &t ) != EOF )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
while ( t -- )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
scanf ( "%d%d", &n, &m );
initm ( 2 * n + 2 );
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for ( int i=1; i<n+1; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
add ( 0, i, 1 );
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for ( i=0; i<m; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
scanf ( "%d%d", &b, &e );
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
add ( b, e+n, 1 );
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for ( i=n+1; i<2*n+1; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
add ( i, 2*n+1, 1 );
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
printf ( "%d\n", n - maxflow ( 0, 2*n+1, 2*n+2 ) );
}
}
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
|
|
| 日 | 一 | 二 | 三 | 四 | 五 | 六 |
---|
24 | 25 | 26 | 27 | 28 | 29 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 1 | 2 | 3 | 4 | 5 |
|
公告
决定从线程开始!!
常用链接
留言簿(6)
随笔档案
搜索
最新评论
![](/images/xml.gif)
阅读排行榜
评论排行榜
|
|