作者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