|
由于该图不是一颗树,所以首先要将一些块压缩成点,所谓块就是没有割点的分量,于是只要求出割边,然后删除,之后对整个图进行Floodfill,得到的连通分量再用割边 补图,得到的图一定是一棵树,然后就可以树形DP了。 #include <iostream>
#define MAXN 100010
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) struct list {
list *next;
int ID;
};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int n, m;
int value[ MAXN ];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
list data[ 1000000 ];
list *vec[ MAXN ];
list *Bri[ MAXN ];
int Ance[ MAXN ];
int Dep[ MAXN ];
int Color[ MAXN ];
int father[ MAXN ];
bool Cut[ MAXN ];
int num[ MAXN ];
#define G 0 // Grey 正在访问
#define B 1 // Black 访问完毕
#define W 2 // White 未曾访问
int root, T;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) /**//*******************求无向图割边割点********************
* list vec[i] 表示原的邻接表 *
* list Bri[i] 保存割边 *
* bool Cut[i] 保存割点 *
* int Ance[i] 保存和i或i的子孙邻接的最高辈分的祖先的深度 *
* int Dep[i] 保存i点所在的深度 *
* int Color[i] 保存当前结点访问情况 *
* int father[i] 保存i的父亲结点的编号 *
* int num[i] 缩点后每个点所在的新块的编号 *
*********************************************************/
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int Min ( int a, int b ) {
return a < b ? a : b;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) void BridgeCut( int key, int depth ) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int son = 0;
Dep[ key ] = depth;
Color[ key ] = G;
Ance[ key ] = depth;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
list *p, *q;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for( p = vec[ key ]->next; p ; p = p->next ) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int next = p->ID;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if( next != father[ key ] && Color[ next ] == G) {
Ance[ key ] = Min( Ance[ key ], Dep[ next ] );
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if( Color[ next ] == W ) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
father[ next ] = key;
BridgeCut( next, depth + 1);
son ++; Ance[ key ] = Min( Ance[ key ], Ance[ next ] );
// 判割点
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if( key == root ) {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if( son > 1 ) {
Cut[ key ] = true;
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) }else {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if( Ance[ next ] >= Dep[ key ] ) {
Cut[ key ] = true;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
// 判割边
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if( Ance[ next ] > Dep[ key ] ) {
q = &data[ T++ ];
q->ID = next;
q->next = Bri[ key ]->next;
Bri[ key ]->next = q;
q = &data[ T++ ];
q->ID = key;
q->next = Bri[ next ]->next;
Bri[ next ]->next = q;
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
Color[ key ] = B;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) void CreateGraph() {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int i, x, y;
T = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i = 1; i <= n; i++)
scanf("%d", &value[i]);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(i = 1; i <= n; i++) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
Bri[i] = &data[ T++ ];
Bri[i]->ID = i;
Bri[i]->next = NULL;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
vec[i] = &data[ T++ ];
vec[i]->ID = i;
vec[i]->next = NULL;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
Ance[i] = INT_MAX;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
Cut[i] = false;
Color[ i ] = W;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
list *p;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while( m-- ) {
scanf("%d %d", &x, &y);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
p = &data[ T++ ];
p->next = vec[x]->next;
p->ID = y;
vec[x]->next = p;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
p = &data[ T++ ];
p->next = vec[y]->next;
p->ID = x;
vec[y]->next = p;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) /**//*
割边割点输出,以及缩块后的图的邻接表
*/
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) void Print() {
list *p;
int i;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(i = 1; i <= n; i++) {
printf("%d: ", i);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(p = Bri[i]->next; p; p = p->next) {
printf("%d ", p->ID);
}
puts("");
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(i = 1; i <= n; i++) {
if( Cut[i] )
printf("point : %d\n", i);
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) /**//*以下是树形DP的过程*/
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) bool IsBridge(int u, int v) {
list *p;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for( p = Bri[u]->next; p ; p = p->next ) {
if( p->ID == v )
return 1;
}
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int F;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
// 分块
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) void dfs( int key ) {
list *p;
num[ key ] = F;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(p = vec[ key ]->next; p ; p = p->next ) {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if( Color[ p->ID ] == W && !IsBridge(key, p->ID) ) {
Color[ p->ID ] = B;
dfs( p->ID );
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) void FloodFill() {
int i;
for(i = 1; i <= n; i++)
Color[i] = W;
F = 1;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(i = 1; i <= n; i++) {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if( Color[i] == W ) {
Color[i] = B;
dfs(i);
F ++;
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
__int64 AllVal[ MAXN ];
__int64 M, zong;
list *New[ MAXN ];
int hash[ MAXN ];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
// TreeDp
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) void Search( int key ) {
list *p;
int son = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for( p = New[ key ]->next; p; p = p->next) {
int q = p->ID;
if( hash[ q ] )
continue;
son ++;
hash[ q ] = 1;
Search(q);
AllVal[ key ] += (__int64)AllVal[ q ];
__int64 a = zong - AllVal[ q ];
__int64 b = AllVal[ q ];
a -= b;
if( a < 0)
a = -a;
if( a < M )
M = a;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) void TreeDp() {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int i;
M = 0;
memset( AllVal, 0, sizeof(AllVal) );
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(i = 1; i <= n; i++) {
AllVal[ num[i] ] += (__int64)value[i];
M += (__int64)value[i];
}
zong = M;
F --;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(i = 1; i <= F; i++) {
New[i] = &data[ T++ ];
New[i]->ID = i;
New[i]->next = NULL;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
list *p, *q;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(i = 1; i <= n; i++) {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(p = Bri[i]->next; p; p = p->next) {
q = &data[ T++ ];
q->ID = num[ p->ID ];
q->next = New[ num[i] ]->next;
New[ num[i] ]->next = q;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
memset( hash, 0, sizeof(hash) );
hash[1] = 1;
Search(1);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int main() {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int i;
int t = 1;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while( scanf("%d %d", &n, &m) != EOF && (n || m) ) {
CreateGraph();
root = 1;
father[ root ] = 0;
BridgeCut( root, 0 );
FloodFill();
//Print();
TreeDp();
printf("Case %d: %I64d\n", t++, M);
}
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
|