knowledgediarybd.com

Your Virtual Knowledge Campus







UVA Graph Problem Solution,uva-255, uva-315,uva-821,uva-10600

graphs-problem-solutionUVA Graph Problem Solution  are more difficult in UVa  Problem set but Graph problem are more important because most of the graph  problem are related  to real life problem. Graph problems are,Graph Traversal,Maximum Flow,Minimum Spanning Tree,Single-Source Shortest Paths ,All-Pairs Shortest Paths, Special Graph (Directed Acyclic Graph) & Special Graphs(Others). Here are the list of some uva Graph Problem Solution,uva-255, uva-315,uva-821,uva-10600

UVA Graph Problem Solution,uva-255, uva-315,uva-821,uva-10600  

are given below:

UVa: 259(Software Allocation)

 

 

#include<stdio.h>
#include<string.h>

char str[100];

struct ss {
int Job[30];
int ind;
}com[12];

int F[30], T, Count[30], A[12];

void Reset() {
int i;
for(i = 0; i<10; i++) {
F[i] = com[i].ind = Count[i] = 0;
}
for(i; i<30; i++)
F[i] = Count[i] = 0;
}

void Set() {
int i, j, k, m;
k = str[0]-'A';
m = str[1] - '0';
F[k] += m;
T += m;
for(i = 3; str[i] != ';'; i++) {
j = str[i] - '0';
com[j].Job[com[j].ind++] = k;
}
}
void Print() {
int i, j;
for(i = 1; i<11; i++) {
j = A[i];
if(j == 28) printf("_");
else printf("%c",j+'A');
}
printf("\n");
}

int BackTrak(int n, int level, int total, int cm) {
int i, j, m, k;
A[level] = cm;
if(level == 10 ) {
if( T == total) {
Print();
return 1;
}
return 0;
}
Count[cm] ++;
for(i = n+1; i<10; i++) {
for(j = 0; j<com[i].ind; j++) {
m = com[i].Job[j];
k = total;
if(m != 28) k = total+1;
if(Count[m] < F[m] || m == 28)
if(BackTrak(i,level+1,k,m)) return 1;
}
}
Count[cm] --;
return 0;
}
void Cal() {
int i, j;
for(i = 0; i<10; i++)
com[i].Job[com[i].ind++] = 28;
if(T>10){
printf("!\n");
return;
}
j = BackTrak(-1,0,0,29);
if(!j) printf("!\n");
}
void main() {
int i;
//freopen("c:\\h.in","r",stdin);
while(gets(str)) {
T = 0;
Set();
while(gets(str)) {
for(i = 0; str[i]; i++) {
if(str[i] == '\n') {
str[i] = NULL;
break;
}
}
if(strlen(str) == 0) break;
Set();
}
Cal();
Reset();
}
}

UVa: 315(NetWork)

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define MAXN 102

int p[MAXN], rank[MAXN];
char L[MAXN][MAXN];

int N, cp;

void Ini() {
int i;
for( i = 1; i<= N; i++){
p[i] = i;
rank[i] = 0;
}
}

int Find(int x) {
if(x != p[x])
p[x] = Find(p[x]);
return p[x];
}

void Link(int x, int y) {
if(rank[x] > rank[y])
p[y] = x;
else {
p[x] = y;
if(rank[x] == rank[y])
rank[y]++;
}
}
void ReadCase() {
char input[1000], *p;
int n, m;
while(gets(input)) {
p = strtok(input," ");
n = atoi(p);
if(!n) break;
while(p) {
p = strtok(NULL," ");
if(p) {
m = atoi(p);
L[n][m] = L[m][n] = 1;
}
}
}
}
void SolvedCase() {
int i, j, k, c = 0;
int x, y, t;
for(i = 1; i<= N; i++) {
Ini();
t = N-1;
for(j = 1; j<N; j++) {
if(j == i) continue;
for(k = j+1; k<= N; k++) {
if(k == i) continue;
if(L[j][k] == 1) {
x = Find(j);
y = Find(k);
if(x != y){
Link(x,y);
t--;
}
}
}
}
if(t-1 >0 ) c++;
}
printf("%d\n",c);
}

void main() {
char input[1000];
int i, j;
while(gets(input)){
sscanf(input,"%d",&N);
if(!N) break;
Ini();
cp = N-1;
ReadCase();
SolvedCase();
for( i = 1; i<= N; i++)
for( j = i+1; j<=N; j++)
L[i][j] = L[j][i] = 0;
}
}

UVa: 821(Page Hopping)

#include<stdio.h>

#define MAX 105
#define MIN(a, b) (a>b?b:a)
#define INF 214748

int Link[MAX][MAX];
int A[MAX], F[MAX];
int maxN;

void Ini() {
int i, j;
for(i = 1; i<= 100; i++) {
for(j = i+1; j<= 100; j++)
Link[i][j] = Link[j][i] = INF;
Link[i][i] = 0;
F[i] = 0;
}
}

void Floyd() {
int i, j, k;
int p, q, r;
for(k = 0; k<maxN; k++) {
p = A[k];
for(i = 0; i< maxN; i++) {
q = A[i];
for(j = 0; j< maxN; j++) {
r = A[j];
Link[q][r] = MIN(Link[q][r], Link[q][p] + Link[p][r]);
}
}
}
}

void Cal(int kase){
int i, j, p, q;
double sum = 0, total;
Floyd();
for(i = 0; i<maxN; i++) {
p = A[i];
for(j = i+1; j< maxN; j++){
q = A[j];
sum += Link[p][q] + Link[q][p];
}
}
total = maxN*(maxN-1);
printf("Case %d: average length between pages = %.3lf clicks\n",kase,sum/total);
}

void main() {
int a, b, kase = 1;
while(1) {
maxN = 0;
scanf("%d%d",&a,&b);
if(!a && !b) break;
Ini();
Link[a][b] = 1;
if(!F[a]) { A[maxN++] = a; F[a] = 1; }
if(!F[b]) { A[maxN++] = b; F[b] = 1; }
while(1) {
scanf("%d%d",&a,&b);
if(!a && !b) break;
Link[a][b] = 1;
if(!F[a]) { A[maxN++] = a; F[a] = 1; }
if(!F[b]) { A[maxN++] = b; F[b] = 1; }
}
Cal(kase++);
}
}

UVa: 10600(ACM Contest and Blackout)

#include<stdio.h>
#include<stdlib.h>

#define MAXN 102
#define MAXE 5055

struct ss {
int u, v;
int weight;
}E[MAXE],MST[MAXE];

int P[MAXN], rank[MAXN];
int N, M;

int com(const void *a, const void *b) {
ss *x = (ss *)a;
ss *y = (ss *)b;
return x->weight - y->weight;
}

int Find(int n) {
if(n != P[n])
P[n] = Find(P[n]);
return P[n];
}

void Link(int x, int y) {
if(rank[x]>rank[y])
P[y] = x;
else {
P[x] = y;
if(rank[x] == rank[y])
rank[y] ++;
}
}

void MakeSet() {
int i;
for(i = 0; i<N; i++) {
rank[i] = 0;
P[i] = i;
}
}

int mSt(int p, int c) {
int sum = 0, i, x, y;
int mstLen = 0;
for(i = 0; i<M && mstLen<N-1; i++) {
if((E[i].u == MST[p].u && E[i].v == MST[p].v)) continue;
x = Find(E[i].u);
y = Find(E[i].v);

if(x != y){
Link(x,y);
sum += E[i].weight;
if(sum > c) return -1;
mstLen++;
}
}
if(mstLen==N-1)
return sum;
return -1;
}

void Cal() {
int i, mstLen = 0, x, y, f = 0;
int Best_1 = 0, Best_2 = 21474836;
MakeSet();
qsort(E,M,sizeof(ss),com);
for(i = 0; i<M && mstLen<N-1; i++) {
x = Find(E[i].u);
y = Find(E[i].v);
if(x != y){
MST[mstLen++] = E[i];
Link(x,y);
Best_1 += E[i].weight;
}
}
printf("%d",Best_1);
for(i = 0; i<mstLen; i++) {
MakeSet();
x = mSt(i,Best_2);
if(x != -1 && x<Best_2 ){
f = 1;
Best_2 = x;
}
}
if(f) printf(" %d\n",Best_2);
else printf(" %d\n",Best_1);

}

void main() {
int kase, i;
//freopen("c:\\in.txt","r",stdin);
scanf("%d",&kase);
while(kase--) {
scanf("%d%d",&N,&M);
for(i = 0; i<M; i++){
scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].weight);
E[i].u--;
E[i].v--;
}
Cal();
}
}

Related Post or You may Like:

  1. Introduction of acm ICPC & UVa Online Judge
  2. Programming Sites & Resources
  3. Introduction & Ad Hoc Problems Solution
  4. Data Structures & Libraries problem Solution
  5. UVa Mathematics Problem Solution
  6. String Processing Problem Solution
  7. Computational Geometry Problem Solution
  8. Other Problem Solution
knowledgediarybd.com © 2017
shares