作者learnerQQ (小铨)
看板C_and_CPP
标题有关图形切割
时间Fri Jun 19 16:14:01 2009
小弟想写一个 程式 就是可以把一个无向图 点和点之间的 waste 记下来
想办法找出 切割方法 把图切割成 两部份
EX: 原图 G(V,E) 切割成 S,S-V
其中 S 和 S-V的 waste 要尽量相等
部分程式码
#include<stdio.h>
#include<stdlib.h>
#define row 11
#define col 11
int main()
{
int i,j,total=0;
int graph[row][col]={0};//以阵列表示 graph
printf("input the waste of edge!");
printf("点到自己请输入 0,无法到达的点请输入 -1\n\n");
for(i=1;i<row;i++) //让使用者输入边的 waste
for(j=1;j<col;j++)
{
printf("input the waste from %d point to %d point\n",i,j);
scanf(" %d",&graph[i][j]);
if(graph[i][j]>=0)
total+=graph[i][j]; //计算 graph的总 waste
}
total/=2; // double count!
printf("the total waste is %d",total);
if(total%2==0)
printf("需将此 V(G,E) 切割成 %d wastes 和 %d wastes两个图\n",total/2,total/2);
else
printf("需将此 V(G,E) 切割成 %d wastes 和 %d wastes两个图\n",total/2,total/2+1);
system("pause");
return 0;
}
请问怎嚜找到 那条切割线呢? 怎知道哪些点 该在 集合 S
哪些点该在 集合 S-V 呢?
先将所有的 waste 给 排序好吗?
EX: 总共 WASTE 为 30
已知边与边的WASTE 2,3,5,5,7,8 //排序过的
30分两半 所以是 15
15-[2]-[3]-[5]-[5]=0 为一集合 S
15-[7]-[8]=0 为一集合 S-V
这样的想法 好吗? 还是有更好的呢? 这是我当下的想法~
麻烦噜 各位
谢谢
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.130.189.12
※ 编辑: learnerQQ 来自: 140.130.189.12 (06/19 16:14)
※ learnerQQ:转录至看板 PLT 06/19 16:28