This code is also another co-worker's source.
He makes it even if he didn't use any algorithm.
He made his own way that he delete the edge which is not the answer
----------------------------------------------------------------------------------------------
#include
#define MAXV 100
#define MAXDEGREE 100
typedef struct {
unsigned int edges[MAXV+1][MAXV+1];
unsigned int nverticies;
unsigned int nedges;
} graph;
graph g;
typedef struct {
unsigned int x;
unsigned int y;
unsigned int value;
} minSt;
minSt minList[10000];
unsigned int minCnt;
int map[100];
int cnt;
void init_graph()
{
memset(&g, 0, sizeof(graph));
}
void set_edges(int i)
{
g.nedges = i;
}
void set_verticies(int i)
{
g.nverticies = i;
}
void set_edge(int x, int y,int weight)
{
g.edges[x][y] = weight;
g.edges[y][x] = weight;
minList[minCnt].x = x;
minList[minCnt].y = y;
minList[minCnt++].value = weight;
}
void sort_min()
{
minSt tmp;
int i,j;
for ( i = 0 ; i < minCnt ; i++ ) {
for ( j = i ; j < minCnt ; j++ ) {
if ( minList[i].value > minList[j].value ) {
tmp = minList[i];
minList[i] = minList[j];
minList[j] = tmp;
}
}
}
#if 0
for ( i = 0 ; i < minCnt ; i++ ) {
printf("x(%d) y(%d) weight(%d)\n",minList[i].x, minList[i].y, minList[i].value);
}
#endif
}
void print_graph()
{
int i,j;
printf("==========================\n");
for ( i = 1 ; i <= g.nverticies ; i++ ) {
for ( j = 1 ; j <= g.nverticies ; j++ ) {
printf("%3d ",g.edges[i][j]);
}
printf("\n");
}
}
unsigned int ConnMap[101][101];
int isConnected2()
{
int i,j,k;
memcpy(ConnMap, g.edges, sizeof(ConnMap));
for ( i = 1 ; i <= g.nverticies ; i++ ) {
for ( j = 1 ; j <= g.nverticies ; j++ ) {
if ( i == j )
continue;
for ( k = 1 ; k <= g.nverticies ; k++ ) {
if ( j == k )
continue;
if ( i == k )
continue;
if ( ConnMap[i][j] > 0 && ConnMap[j][k] > 0 ) {
ConnMap[i][j] = 1;
ConnMap[j][i] = 1;
ConnMap[j][k] = 1;
ConnMap[k][j] = 1;
ConnMap[i][k] = 1;
ConnMap[k][i] = 1;
}
}
}
}
#if 0
printf("==========================\n");
for ( i = 1 ; i <= g.nverticies ; i++ ) {
for ( j = 1 ; j <= g.nverticies ; j++ ) {
printf("%3d ",ConnMap[i][j]);
}
printf("\n");
}
exit(0);
#endif
}
int isConnected(int start,int end)
{
register unsigned int i,j;
register unsigned int check=0;
if ( start == end )
return 1;
#if 1
if ( g.edges[start][end] > 0 ) {
return 1;
}
#endif
for ( i = 1 ; i <= g.nverticies ; i++ ) {
if ( i == start )
continue;
check = 0;
for ( j = 0 ; j < cnt ; j++ ) {
if ( map[j] == i ) {
check=1;
break;
}
}
if ( check == 1 )
continue;
if ( g.edges[start][i] > 0) {
map[cnt]=start;
cnt++;
if (isConnected(i,end) == 1 ) {
return 1;
}
}
}
return 0;
}
void del_edge(int x,int y)
{
g.edges[x][y] = 0;
g.edges[y][x] = 0;
}
int main()
{
int edge;
int vert;
int x,y;
int i,weight;
int start, end, people;
int min;
int scenario=1;
while(1) {
init_graph();
scanf("%d %d",&vert,&edge);
if ( vert == 0 )
break;
if ( vert < 1 || vert > 100 )
continue;
set_verticies(vert);
set_edges(edge);
for ( i = 0 ; i < edge ; i++ ) {
scanf("%d %d %d",&x,&y,&weight);
set_edge(x,y,weight);
}
scanf("%d %d %d",&start,&end,&people);
sort_min();
cnt = 0;
i = 0;
while ( isConnected(start,end)) {
#if 0
while ( 1 ) {
isConnected2();
if ( ConnMap[start][end] == 0 )
break;
#endif
cnt = 0;
min = minList[i].value;
del_edge(minList[i].x,minList[i].y);
i++;
}
if ( people % (min-1 ) == 0 )
min = people/(min-1);
else
min = people/(min-1) + 1;
printf("Scenario #%d\n",scenario++);
printf("Minimum Number of Trips = %d\n\n",min);
minCnt = 0;
fflush(stdin);
}
return 0;
}
#if 0
int find_min(int *x, int *y)
{
int i,j;
int min=99999;
int a;
for ( i = 1 ; i <= g.nverticies ; i++ ) {
for ( j = 1 ; j <= g.nverticies ; j++ ) {
if ( g.edges[i][j] > 0 && g.edges[i][j] < min ){
min = g.edges[i][j];
*x = i;
*y = j;
}
}
}
return min;
}
#endif
'ACM' 카테고리의 다른 글
| [Accept] 850 Crypt Kicker II (0) | 2009.06.02 |
|---|---|
| [Accept] 10132 File Fragmentation (0) | 2009.06.02 |
| [Accept] 10099 - The Tourist Guide (0) | 2009.06.02 |
| [Time Limit] 10099 - The Tourist Guide (0) | 2009.06.02 |
| [Accept] 10004 - Bicoloring problem (0) | 2009.06.02 |
Unfortunately, I didn't get accept from Judge Server.
This code is one of my co-worker's source.
He used Dynamic Programming.
I should study that algorithm.
----------------------------------------------------------------------------------------------
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 32 33 34 35 36 37 38 39 40 41 42 43 |
#include <stdio.h> int g_cities[101][101]; #define MIN(a,b) (a>b?b:a) int search_min_trips(int start, int end, int num_cities) { int i, j, k; int max = 0, min; for (i = 1; i <= num_cities; i++) { for (j = 1; j <= num_cities; j++) { for (k = 1; k <= num_cities; k++) { min = MIN(g_cities[i][k], g_cities[k][j]); if (g_cities[i][j] < min) g_cities[i][j] = g_cities[j][i] = min; }}} return g_cities[start][end]; } int main() { int i, cnt = 0; int num_cities; int num_roads; int num_passengers; int start, end; int city1, city2, cap; int max_cap; while (scanf("%d %d", &num_cities, &num_roads) != 1 && num_cities != 0 && num_roads != 0) { memset(g_cities, 0x00, sizeof(g_cities)); for (i = 0; i < num_roads; i++) { scanf("%d %d %d", &city1, &city2, &cap); g_cities[city1][city2] = g_cities[city2][city1] = cap; } scanf("%d %d %d", &start, &end, &num_passengers); max_cap = search_min_trips(start, end, num_cities) - 1; printf("Scenario #%d\n", ++cnt); printf("Minimum Number of Trips = %d\n\n", num_passengers / max_cap + (num_passengers % max_cap == 0 ? 0 : 1)); } return 0; } |
'ACM' 카테고리의 다른 글
| [Accept] 10132 File Fragmentation (0) | 2009.06.02 |
|---|---|
| [Accept] 10099 - The Tourist Guide (0) | 2009.06.02 |
| [Time Limit] 10099 - The Tourist Guide (0) | 2009.06.02 |
| [Accept] 10004 - Bicoloring problem (0) | 2009.06.02 |
| [Accept] 100 - The 3n+1 problem (0) | 2009.06.02 |
#include <stdio.h> #define MAX_CITY 101 #define DISCONNECTED 0 #define PASSED 1 #define NOTPASSED 0 typedef struct TourInfo{ int roadNum; // road Number (input) int cityNum; // city Number (input) int roadInfo[MAX_CITY][MAX_CITY]; // road info (max passenger info) int cityIsPassed[MAX_CITY]; // passed or not passed int cityMinNum[MAX_CITY]; // min Passenger Number int startCity; // start (input) int destCity; // destination (input) int totalPassengerNum; // total passenger Number (input) int minPassengerNum; // result }TourInfo; void initTourInfo(); int findMinNumberOfTrips(int left); TourInfo tour; int main(void) { int firstCity, secondCity, maxPassengerNum; int scenarioCount=0, result, i; while(1){ scanf("%d %d", &tour.cityNum, &tour.roadNum); if(tour.cityNum==0 && tour.roadNum==0) break; result = 0; initTourInfo(); for(i=0; i<tour.roadNum; i++){ scanf("%d %d %d", &firstCity, &secondCity, &maxPassengerNum); tour.roadInfo[firstCity][secondCity] = maxPassengerNum; tour.roadInfo[secondCity][firstCity] = maxPassengerNum; } scanf("%d %d %d", &tour.startCity, &tour.destCity, &tour.totalPassengerNum); if(tour.totalPassengerNum < 1) break; findMinNumberOfTrips(tour.startCity); scenarioCount++; result = tour.totalPassengerNum / (tour.minPassengerNum-1); if(tour.totalPassengerNum % (tour.minPassengerNum-1)) result++; printf("Scenario #%d\n", scenarioCount); printf("Minimum Number of Trips = %d\n\n", result); } return 0; } int findMinNumberOfTrips(int left) { int i, right, minPass; tour.cityIsPassed[left]=PASSED; // Last City if(left==tour.destCity){ if(!tour.minPassengerNum) { tour.minPassengerNum = tour.cityMinNum[left]; } else { if(tour.minPassengerNum < tour.cityMinNum[left]) { tour.minPassengerNum = tour.cityMinNum[left]; } } tour.cityMinNum[left]=NOTPASSED; tour.cityIsPassed[left]=NOTPASSED; return 1; } for(right=1; right<=tour.cityNum; right++) { if(tour.cityIsPassed[right]==PASSED) continue; // already passed city if(tour.roadInfo[left][right]!=0) // CONNECTED { if(!tour.cityMinNum[left]){ // first path tour.cityMinNum[right] = tour.roadInfo[left][right]; } else{ if(tour.cityMinNum[left] > tour.roadInfo[left][right]){ tour.cityMinNum[right] = tour.roadInfo[left][right]; } else{ tour.cityMinNum[right] = tour.cityMinNum[left]; } } if(tour.minPassengerNum >= tour.cityMinNum[right]) continue; findMinNumberOfTrips(right); } } // init and return tour.cityMinNum[left]=NOTPASSED; tour.cityIsPassed[left]=NOTPASSED; return 1; } void initTourInfo() { int i,j; for(i=0; i<MAX_CITY; i++) { for(j=0; j<MAX_CITY; j++) { tour.roadInfo[i][j] = DISCONNECTED; } tour.cityIsPassed[i] = NOTPASSED; tour.cityMinNum[i] = NOTPASSED; } tour.minPassengerNum = 0; }
'ACM' 카테고리의 다른 글
| [Accept] 10099 - The Tourist Guide (0) | 2009.06.02 |
|---|---|
| [Accept] 10099 - The Tourist Guide (0) | 2009.06.02 |
| [Accept] 10004 - Bicoloring problem (0) | 2009.06.02 |
| [Accept] 100 - The 3n+1 problem (0) | 2009.06.02 |
| 10006 - Carmichael Numbers (0) | 2009.06.02 |