最小费用最大流,地址: http://acm.pku.edu.cn/JudgeOnline/problem?id=2195
#include <stdio.h>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int MAX = 3276700;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int LEN = 205;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int house[LEN][2];
int hl;
int man[LEN][2];
int ml;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void init ()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
hl = ml = 0;
}
![](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;
int weight;
}map[LEN][LEN];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int 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) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for ( int i=0; i<n; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
nearl[i][0] = 1;
for ( int j=0; j<n; j++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
map[i][j].c = map[i][j].f = map[i][j].weight = 0;
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void add ( int a, int b, int c, int weight )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if ( ! map[a][b].c && ! map[b][a].c )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
nearl[a][ nearl[a][0]++ ] = b;
nearl[b][ nearl[b][0]++ ] = a;
}
map[a][b].c += c;
map[a][b].weight += weight;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int cost[LEN];
int road[LEN];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int ad ( int s, int t, int *mincost )
![](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 p = t;
int min = MAX;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
while ( p != s )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if ( min > map[ road[p] ][p].c - map[ road[p] ][p].f )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
min = map[ road[p] ][p].c - map[ road[p] ][p].f;
}
p = road[p];
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
p = t;
while ( p != s )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
map[ road[p] ][p].f += min;
map[ p ][ road[p] ].f -= min;
*mincost += min * map[ road[p] ][p].weight;
p = road[p];
}
return min;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int mima ( int s, int t, int n, int *mincost )
![](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 maxflow = 0;
*mincost = 0;
do
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
road[t] = -1;
cost[s] = 0;
for ( int i=1; i<n; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
cost[i] = MAX;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int flag = 1;
while ( flag )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
flag = 0;
for ( int v=0; v < n; v++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
for ( int u=1; u<nearl[v][0]; u++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if ( map[ nearl[v][u] ][v].f < map[ nearl[v][u] ][v].c && cost[ nearl[v][u] ] < MAX )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if ( cost[v] > cost[ nearl[v][u] ] + map[ nearl[v][u] ][v].weight )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
cost[v] = cost[ nearl[v][u] ] + map[ nearl[v][u] ][v].weight;
road[v] = nearl[v][u];
flag = 1;
}
}
}
}
}
if ( road[t] != -1 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
maxflow += ad ( s, t, mincost );
}
}while ( road[t] != -1 );
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return maxflow;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int abs ( int a )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return a > 0 ? a : -a;
}
![](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 n, m;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
while ( scanf ( "%d%d", &n, &m ) != EOF && ( n || m ) )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
int i, j;
char in[105];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
gets ( in );
init ();
for ( i=0; i<n; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
scanf ( "%s", &in );
for ( j=0; j<m; j++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if ( in[j] == 'H' )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
house[hl][0] = i;
house[hl][1] = j;
hl ++;
continue;
}
if ( in[j] == 'm' )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
man[ml][0] = i;
man[ml][1] = j;
ml ++;
continue;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
initm ( ml+hl+2 );
for ( i=0; i<ml; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
add ( 0, i+1, 1, 0 );
add ( +1, 0, 0, 0 );
}
for ( i=0; i<ml; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
for ( j=0; j<hl; j++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
int weight = abs ( man[i][0]-house[j][0] ) + abs ( man[i][1]-house[j][1] );
add ( i+1, ml+1+j, 1, weight );
add ( ml+1+j, i+1, 0, -weight );
}
}
for ( j=0; j<hl; j++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
add ( ml+1+j, ml+hl+1, 1, 0 );
add ( ml+hl+1, ml+1+j, 0, 0 );
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int mincost;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
mima ( 0, ml+hl+1, ml+hl+2, &mincost );
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
printf ( "%d\n", mincost );
}
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](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)
阅读排行榜
评论排行榜
|
|