<input>

n

nxn matrix

16

387 120 190 124 376 339 452 425 126 11 289 327 353 451 295 119 

204 487 377 332 45 432 225 153 420 85 318 276 143 315 323 327 

394 113 373 63 221 425 93 425 329 389 457 141 204 359 7 459 

90 461 170 66 388 154 381 445 134 134 333 156 174 63 198 239 

288 473 284 22 455 295 156 375 430 192 197 0 146 42 478 382 

48 130 43 467 29 316 421 185 405 130 98 435 467 56 365 313 

268 175 271 449 413 215 1 371 143 252 185 448 412 465 88 315 

481 258 282 49 184 449 225 109 298 237 80 283 187 361 378 168 

240 371 59 135 389 381 124 190 91 175 381 481 399 109 456 278 

104 380 52 385 324 207 407 149 491 100 434 215 261 79 21 424 

327 178 162 425 32 305 458 13 4 336 233 134 467 387 35 390 

340 303 416 183 84 263 216 436 471 228 197 393 276 230 15 500 

450 291 173 5 264 321 69 124 131 385 367 97 324 326 216 363 

17 405 0 407 359 14 336 91 136 9 288 131 379 352 217 4 

250 478 473 7 249 394 258 190 218 443 99 2 349 477 213 307 

181 239 438 164 193 383 181 143 492 498 217 80 268 207 308 350 

<output>

sorting된 순서

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

int arr[100][100];

int n;

void sort(int row,int type)

{

int i,j,temp;

if (type == 0)

{

for (i=0; i<n;i++)

{

for (j = i%2; j<n; j+=2)

{

if (j+1 < n && arr[row][j] > arr[row][j+1])

{

temp = arr[row][j];

arr[row][j] = arr[row][j+1];

arr[row][j+1] = temp;

}

}

}

}

else

{

for (i=0; i<n;i++)

{

for (j = i%2; j<n; j+=2)

{

if (j+1 < n && arr[row][j] < arr[row][j+1])

{

temp = arr[row][j];

arr[row][j] = arr[row][j+1];

arr[row][j+1] = temp;

}

}

}

}

}

void sortcol(int col)

{

int i,j,temp;

for (i=0; i<n;i++)

{

for (j = i%2; j<n; j+=2)

{

if (j+1 < n && arr[j][col] > arr[j+1][col])

{

temp = arr[j][col];

arr[j][col] = arr[j+1][col];

arr[j+1][col] = temp;

}

}

}

}

int main(void)

{

int i,j;

int logn;

// n

// nxn matrix

FILE* f = fopen ("input3.txt","r");

fscanf (f,"%d",&n);

for (i=0;i<n;i++){

for (j=0;j<n;j++)

fscanf (f,"%d",&arr[i][j]);}

logn = log( (double)n ) / log( (double)2 );

for (i=0;i<logn;i++)

{

for (j=0;j<n;j++)

{

sort(j,j%2);

}

for (j=0;j<n;j++)

{

sortcol(j);

}

}

for (j=0;j<n;j++)

{

sort(j,0);

}

for (i=0;i<n;i++)

{

for (j=0;j<n;j++)

{

printf ("%3d ",arr[i][j]);

}

printf ("\n");

}

}

입력 출력같음 (빈갯수가 2^n아님)

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

int arr[100];

int tree[100];

int offset;// 2 * s - 1

int s; // 2^ (c(log2(n)) -1)

int lowext; // 2*( (n-1) - (s-1))

void init(int n, int size)

{

int i=0;

int k;

int p;

double l;

int ce;

l=log( (double)n ) / log( (double)2 );

ce = ceil(l);

s = pow((double)2, ( ce -1 ));

offset = 2*s-1;

lowext = 2*((n-1) - (s-1));

for (i=1;i<=n;i++)

{

arr[i] = size;

}

if (n%2 == 0)

{

for (k=1;k<=n;k++)

{

if (k%2==1)

{

if (k<=lowext)

p = (k+offset) / 2;

else

p = (k-lowext + n-1)/2;

tree[p] = k;

}

}

}

else

{

for (k=1;k<=lowext; k+=2)

{

if (k<=lowext)

p = (k+offset) / 2;

else

p = (k-lowext + n-1)/2;

tree[p] = k;

}

for (k=lowext +2; k<=n; k+=2)

{

p=(s+n-1-s+k-lowext)/2;

//p= (s+(k-lowext)) /2;

tree[p] = k;

}

}

/*

for (i=1;i<=n;i++){

if (i%2 == 1)

tree[ (i+n-1)/2 ] = i;

}

*/

for (i= (n-1)/2; i>0; i--)

{

tree [i] = tree[i*2];

}

}

int main(void)

{

int i,j;

int n;

int cnt,size;

//빈개수, n(오브젝트 개수), 빈사이즈 

FILE* f = fopen ("input2.txt","r");

fscanf (f,"%d %d %d",&cnt,&n,&size);

// arr = (int *)malloc(sizeof(int)*cnt+1);

// tree = (int *)malloc(sizeof(int)*cnt);

init(cnt,size);

for (i=1;i<cnt;i++)

{

printf ("%d ",tree[i]);

}

for (i=0;i<n;i++)

{

int a;

int idx;

int parent;

fscanf (f,"%d",&a);

idx = 1;

while(1)

{

if ( arr[tree[idx]] >= a)

{

idx = idx*2;

if (idx >=cnt)

{

idx /=2;

break;

}

if (arr[tree[idx]]<a)

{

idx /=2;

idx = idx*2+1;

}

if (idx >=cnt)

{

idx /=2;

break;

}

/*

if (idx *2 >=cnt)

break;

if (arr[tree[idx*2]] <a)

{

if (idx*2+1 >= cnt)

break;

idx = idx*2+1;

}

else

{

idx = idx*2;

}

*/

}

else

{

idx = idx*2+1;

if (idx*2+1 >= cnt)

{

idx = (idx-1)/2;

break;

}

}

}

if (tree[idx]%2 == 0 && arr[tree[idx]-1] >= a)

{

arr[tree[idx]-1] -=a;

parent = idx-1;

}

else

{

arr[tree[idx]] -= a;

parent = idx;

}

/*

if (arr[tree[idx]] >a)

arr[tree[idx]] -= a;

else

arr[tree[idx]] -= a;

*/

/*

if (tree[idx] %2 == 0)

{

if (arr[tree[idx]] > arr[tree[idx]-1])

tree[idx] = tree[idx];

else

tree[idx] = tree[idx]-1;

}

else

{

if (arr[tree[idx]] > arr[tree[idx]+1])

tree[idx] = tree[idx];

else

tree[idx] = tree[idx]+1;

}

*/

while(1)

{

int lc;

int rc;

lc = parent*2;

rc = parent*2+1;

if (lc > cnt-1)

{

if (lc>offset)

{

lc=lc-offset;

}

else

{

//lc=lc-lowext;

lc=(lc+lowext - (cnt-1));

}

}

else

{

lc = tree[lc];

}

if (rc > cnt-1)

{

if (rc>offset)

{

rc=rc-offset;

}

else

{

//rc=rc-lowext;

rc=(rc+lowext - (cnt-1));

}

}

else

{

rc = tree[rc];

}

if (arr[lc] >= arr[rc])

{

tree[parent] = lc;

}

else

{

tree[parent] = rc;

}

/*

if (parent*2>cnt-1)

{

tree[parent] = 

tree[parent] = arr[parent*2 - (offset)] >= arr[parent*2-(offset)+1] ? parent*2 - (offset) : parent*2-(offset)+1;

}

else

{

lc = arr[tree[parent*2]];

if (parent*2+1 > cnt-1)

rc =  (parent*2+1)-lowext ;

else

rc = tree[parent*2+1];

tree[parent] = (lc >= arr[rc]) ? tree[parent*2] : rc;

}

*/

parent/=2;

if (parent<1)

break;

}

printf ("\nret : %d",a);

for (j=1;j<cnt;j++)

{

// printf ("%d ",tree[j]);

}

printf ("\n");

for (j=1;j<=cnt;j++)

{

printf ("%d ",arr[j]);

}

printf ("\n");

}

}

빈개수(32)(2^k), n(오브젝트 개수), 빈사이즈 

<input>

32 30 20

10

8

13

10

10

11

14

5

15

13

11

6

19

20

15

18

10

12

16

11

4

13

16

8

20

10

15

1

6

7

<output>

1 2 0 3 2 5 1 1 1 0 5 2 0 1 4 9 7 4 0 5

#include <stdio.h>

#include <stdlib.h>

int* arr;

int* tree;

void init(int n, int size)

{

int i=0;

for (i=1;i<=n;i++)

{

arr[i] = size;

}

for (i=1;i<=n;i++){

if (i%2 == 1)

tree[ (i+n-1)/2 ] = i;

}

for (i= (n-1)/2; i>0; i--)

{

tree [i] = tree[i*2];

}

}

int main(void)

{

int i,j;

int n;

int cnt,size;

//빈개수(32)(2^k), n(오브젝트 개수), 빈사이즈 

FILE* f = fopen ("input.txt","r");

fscanf (f,"%d %d %d",&cnt,&n,&size);

arr = (int *)malloc(sizeof(int)*cnt+1);

tree = (int *)malloc(sizeof(int)*cnt);

init(cnt,size);

for (i=1;i<cnt;i++)

{

printf ("%d ",tree[i]);

}

for (i=0;i<n;i++)

{

int a;

int idx;

int parent;

fscanf (f,"%d",&a);

idx = 1;

while(1)

{

if ( arr[tree[idx]] >= a)

{

if (idx *2 >=cnt)

break;

if (arr[tree[idx*2]] <a)

{

idx = idx*2+1;

}

else

idx = idx*2;

}

else

{

if (idx*2+1 >= cnt)

break;

idx = idx*2+1;

}

}

if (tree[idx]%2 == 0 && arr[tree[idx]-1] >= a)

{

arr[tree[idx]-1] -=a;

}

else

arr[tree[idx]] -= a;

/*

if (arr[tree[idx]] >a)

arr[tree[idx]] -= a;

else

arr[tree[idx]] -= a;

*/

parent = idx;

while(1)

{

int lc;

int rc;

if (parent*2>cnt-1)

tree[parent] = arr[parent*2 - (cnt-1)] >= arr[parent*2-(cnt-1)+1] ? parent*2 - (cnt-1) : parent*2-(cnt-1)+1;

else

tree[parent] = (arr[tree[parent*2]] >= arr[tree[parent*2+1]]) ? tree[parent*2] : tree[parent*2+1];

parent/=2;

if (parent<1)

break;

}

printf ("\nret : ");

for (j=1;j<cnt;j++)

{

// printf ("%d ",tree[j]);

}

printf ("\n");

for (j=1;j<=cnt;j++)

{

if (arr[j] == size)

break;

printf ("%d ",arr[j]);

}

printf ("\n");

}

}

input

16 

97 4 100 

105 15 110 

96 7 96 

98 6 103 

99 13 101 

89 15 91 

100 14 102 

102 12 106 

103 11 107 

95 9 95 

79 3 78 

82 19 79 

87 16 90 

15 1 9 

29 8 34 

5 2 7  

output

total : 15

2 9 8 7 5 1 3 10 6 13 12 11 15 14 16

height : 149

#include <stdio.h>

#include <stdlib.h>

#include <memory.h>

struct node

{

int w;

int end;

struct node* next;

};

int visited[100];

struct node* adj;

int v,e;

int ordered[100];

int vertex;

int d[1000];

int p[1000];

void dfs(int i);

node* insert_adj(int a, int b, int w);

void topolo(int i);

void relax(int u,int v,int w);

void print_path(int i,int cnt);

int main(void)

{

int i,j;

int a[100],h[100],w[100];

int n;

FILE* fin = fopen("input.txt","r");

fscanf (fin,"%d",&n);

v=n+2;

adj = (node*)malloc(sizeof(node)*(v));

for (i=0;i<v;i++){

adj[i].end=-1;

adj[i].w=0;

adj[i].next=NULL;

d[i]=-1;

p[i]=-1;

}

for (i=0;i<n;i++)

{

fscanf (fin,"%d %d %d",&a[i],&h[i],&w[i]);

//insert_adj(a,b,w);

//insert_adj(b,a,w);

}

for (i=0;i<n;i++)

{

insert_adj(0,i+1,0);

for (j=0;j<n;j++)

{

if (i!=j && a[i]>a[j] && w[i]>w[j])

{

insert_adj(i+1,j+1,h[i]);

}

}

insert_adj(i+1,v-1,h[i]);

}

vertex=v-1;

topolo(0);

d[0]=0;

printf ("topological sort : ");

for (i=0;i<v;i++)

{

printf ("%d ",ordered[i]);

}

printf ("\n");

for (i=0;i<v;i++)

{

int cur = ordered[i];

node* temp = &adj[cur];

while( temp!=NULL && temp->end != -1){

relax(cur,temp->end,temp->w);

temp=temp->next;

}

}

printf ("dist : ");

for (i=0;i<v;i++)

{

printf ("%d ",d[i]);

}

printf ("\n\n");

print_path(p[v-1],0);

printf ("\n");

printf ("height : %d\n",d[v-1]);

return 0;

}

void print_path(int i,int cnt)

{

if (i==0)

{

printf ("total : %d\n",cnt);

return;

}

else

{

print_path(p[i],cnt+1);

printf("%d ",i);

}

}

void relax(int u,int v,int w)

{

if (d[v] < d[u]+w)

{

d[v]=d[u]+w;

p[v]=u;

}

}

void topolo(int i)

{

node* temp=&adj[i];

visited[i]=1;

while(temp!=NULL)

{

if (visited[temp->end] == 0 && temp->end != -1)

{

topolo(temp->end);

}

temp=temp->next;

}

ordered[vertex--]=i;

}

node* insert_adj(int a, int b, int w){

node* temp;

node* z;

if (adj[a].end == -1){

adj[a].end=b;

adj[a].w=w;

adj[a].next=NULL;

return &adj[a];

}

temp=&adj[a];

while(temp->next != NULL){

temp=temp->next;

}

z = (node*)malloc(sizeof(node));

z->end=b;

z->w=w;

z->next=NULL;

temp->next=z;

return z;

}

#include <stdio.h>

#include <stdlib.h>

#include <memory.h>

struct node

{

int w;

int end;

struct node* next;

};

int visited[100];

struct node* adj;

int v,e;

int ordered[100];

int vertex;

int d[1000];

int p[1000];

void dfs(int i);

node* insert_adj(int a, int b, int w);

void topolo(int i);

void relax(int u,int v,int w);

int main(void)

{

int i,j;

int a,b,w;

FILE* fin = fopen("input.txt","r");

fscanf (fin,"%d %d",&v,&e);

adj = (node*)malloc(sizeof(node)*(v+1));

for (i=0;i<=v;i++){

adj[i].end=-1;

adj[i].w=0;

adj[i].next=NULL;

d[i]=987654321;

p[i]=-1;

}

for (i=0;i<e;i++)

{

fscanf (fin,"%d %d %d",&a,&b,&w);

insert_adj(a,b,w);

//insert_adj(b,a,w);

}

vertex=v-1;

topolo(0);

d[0]=0;

printf ("topological sort : ");

for (i=0;i<v;i++)

{

printf ("%d ",ordered[i]);

}

printf ("\n");

for (i=0;i<v;i++)

{

int cur = ordered[i];

node* temp = &adj[cur];

while( temp!=NULL && temp->end != -1){

relax(cur,temp->end,temp->w);

temp=temp->next;

}

}

printf ("dist : ");

for (i=0;i<v;i++)

{

printf ("%d ",d[i]);

}

printf ("\n");

return 0;

}

void relax(int u,int v,int w)

{

if (d[v]> d[u]+w)

{

d[v]=d[u]+w;

p[v]=u;

}

}

void topolo(int i)

{

node* temp=&adj[i];

visited[i]=1;

while(temp!=NULL)

{

if (visited[temp->end] == 0 && temp->end != -1)

{

topolo(temp->end);

}

temp=temp->next;

}

ordered[vertex--]=i;

}

node* insert_adj(int a, int b, int w){

node* temp;

node* z;

if (adj[a].end == -1){

adj[a].end=b;

adj[a].w=w;

adj[a].next=NULL;

return &adj[a];

}

temp=&adj[a];

while(temp->next != NULL){

temp=temp->next;

}

z = (node*)malloc(sizeof(node));

z->end=b;

z->w=w;

z->next=NULL;

temp->next=z;

return z;

}

void dfs(int i)

{

if (visited[i] != -1)

return;

else

{

node* t=&adj[i];

visited[i]=1;

while( t!=NULL &&t->end != 0 )

{

if (visited[t->end] == -1){

dfs(t->end);

}

t=t->next;

}

}

}

input

한번에 갈수있는거리

정비소개수

정비소사이거리

정비시간

200

10

70 40 100 190 20 80 60 130 110 30 180

10 5 15 21 3 11 7 17 14 4

output

69

6

2 3 4 7 8 10

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

#include <memory.h>

int d[1000];//무한초기화

int p[1000];//-1초기화

int mdi;

int n;

int a[1000];

int m[1000];

int sum1;

int sum2;

void relax(int u,int v,int w)

{

if (d[v]> d[u]+w)

{

d[v]=d[u]+w;

p[v]=u;

}

}

void print(int cur)

{

if (cur == 0)

return;

else

{

print(p[cur]);

sum1+=m[cur];

sum2++;

printf("%d ",cur);

}

}

int main(void)

{

int i,j;

FILE *fin=fopen("input.txt","r");

fscanf (fin,"%d",&mdi);

fscanf (fin,"%d",&n);

for (i=1;i<n+2;i++)

fscanf (fin,"%d",&a[i]);

for (i=1;i<n+1;i++)

fscanf (fin,"%d",&m[i]);

for (int i=0;i<n+10;i++){

d[i]=987654321;

p[i]=-1;

}

d[0]=0;

i=0;

for (i=0 ; i<n+1 ; i++)

{

int curdist=0;

for (j=i+1;j<=n+1;j++)

{

curdist += a[j];

if (curdist > mdi)

break;

relax(i,j,m[j]);

}

}

print(p[n+1]);

printf ("\n%d\n",sum1);

printf ("%d\n",sum2);

}

input

왼쪽 개수, 오른쪽 개수, edge수

각각의 edge는 왼쪽num -> 오른쪽 num

10 15 31

1 1

2 1

2 3

3 2

3 3

3 4

4 3

4 7

4 8

4 9

4 10

5 7

5 9

5 13

5 14

6 8

6 9

6 12

7 10

7 13

7 14

7 15

8 6

8 8

8 10

9 4

9 10

9 15

10 10

10 11

10 12

output

Max Flow is 10

#include <stdio.h>

#include <stdlib.h>

#include <memory.h>

struct node

{

int end;

int flow;

int cap;

struct node* next;

struct node* pair;

};

typedef struct node node;

int queue[1000];

int front;

int tail;

int pd[1000];

int pb[1000];

int visited[1000];

struct node* adj;

int v,e;

int n,m,edge;

node* insert_adj(int a, int b, int w,int c);

void dfs(int i);

int bfs(int i);

int inqueue(int a);

int dequeue();

int main(void)

{

int i,sum=0,j;

int num=0;

int startpoint;

struct node *temp1,*temp2;

FILE* fin = fopen("bipar_input2.txt","r");

node* t;

//fscanf (fin,"%d %d",&v,&e);

if (fin==NULL){

printf ("파일이없음\n");

exit(0);

}

fscanf (fin,"%d %d %d",&n,&m, &edge);

v=n+m;

adj = (node*)malloc(sizeof(node)*(v+3));

//adj = (node*)malloc(sizeof(node)*(n*n*2+2));

for (i=0;i<=v+2;i++){

adj[i].end=-1;

adj[i].flow=0;

adj[i].cap=0;

adj[i].next=NULL;

}

for (i=0;i<edge;i++)

{

int left,right;

fscanf (fin,"%d %d",&left, &right);

temp1 = insert_adj(0,left,0,1);

temp2 = insert_adj(left,0,0,0);

temp1->pair = temp2;

temp2->pair = temp1;

temp1 = insert_adj(left,n+right,0,1);

temp2 = insert_adj(n+right,left,0,0);

temp1->pair = temp2;

temp2->pair = temp1;

temp1 = insert_adj(n+right,v+1,0,1);

temp2 = insert_adj(v+1,n+right,0,0);

temp1->pair = temp2;

temp2->pair = temp1;

}

/*

for (i=0;i<e;i++)

{

struct node *temp1,*temp2;

fscanf (fin,"%d %d %d",&a,&b,&c);

temp1=insert_adj(a,b,0,c);

temp2=insert_adj(b,a,0,0);

temp1->pair = temp2;

temp2->pair = temp1;

//insert_adj(b,a,w);

}

*/

memset(visited,-1,sizeof(visited));

memset(pd,-1,sizeof(pd));

memset(pb,-1,sizeof(pb));

memset(visited,-1,sizeof(visited));

/*

for (int i=0;i<v;i++)

{

node* t=&adj[i];

while(t!=NULL)

{

printf ("<%d %d %d (%d)> ",i,t->end,t->cap,t->pair->cap);

t=t->next;

}

printf ("\n");

}

*/

while(1)

{

int minflow;

memset(visited,-1,sizeof(visited));

memset(queue,0,sizeof(queue));

front=tail=0;

inqueue(0);

minflow=bfs(0);

printf ("minflow : %d\n",minflow);

/*for (i=0;i<=v+2;i++)

{

printf ("%d ",pb[i]);

}

printf ("\n\n");*/

if ( visited[v+1] == -1 )

break;

else

{

int child = v+1;

int parent = pb[child];

node* t=&adj[child];

printf ("%d %d ",child,parent);

while (parent != 0)

{

t=&adj[parent];

while(t!=NULL){

if (t->end == child)

break;

t=t->next;}

t->flow += minflow;

t->pair->flow += -minflow;

child=parent;

parent = pb[child];

printf ("%d ",parent);

}

printf ("\n\n");

/*

while(t!=NULL){

if (t->end == parent)

break;

t=t->next;}

t->flow += -minflow;

t->pair->flow += +minflow;

*/

t=&adj[0];

while(t!=NULL){

if (t->end == child)

break;

t=t->next;}

t->flow += minflow;

t->pair->flow += -minflow;

}

}

node* temp = &adj[v+1];

while (temp!= NULL)

{

sum += temp->pair->flow;

temp = temp->next;

}

printf ("max flow is : %d\n",sum);

return 0;

}

node* insert_adj(int a, int b, int w,int c){

node* temp;

node* z;

if (adj[a].end == -1){

adj[a].end=b;

adj[a].flow=w;

adj[a].cap=c;

adj[a].next=NULL;

return &adj[a];

}

temp=&adj[a];

while(temp->next != NULL)

{

if (temp->end == b)

{

temp->cap=c;

return temp;

}

temp=temp->next;

}

if (temp->end == b)

{

temp->cap=c;

return temp;

}

z = (node*)malloc(sizeof(node));

z->end=b;

z->flow=w;

z->cap=c;

z->next=NULL;

temp->next=z;

return z;

}

int bfs(int i)

{

int z = dequeue();

int min=987654321;

while( z!=-987654321)

{

node* t = &adj[z];

while(t!=NULL &&t->end != -1)

{

if (t->cap-t->flow > 0 && visited[t->end] == -1)

{

//printf ("%d %d\n",t->end,t->cap - t->flow);

if (t->cap - t->flow <min)

min=t->cap-t->flow;

if (t->end == v+1){

visited[t->end] = 1;

pb[t->end]=z;

return min;

}

visited[t->end] = 0;

pb[t->end] = z;

inqueue(t->end);

}

t=t->next;

}

visited[z] = 1;

z=dequeue();

}

return min;

}

void dfs(int i)

{

if (visited[i] != -1)

return;

else

{

node* t=&adj[i];

visited[i]=1;

while( t!=NULL &&t->end != -1 )

{

if (visited[t->end] == -1){

pd[t->end]=i;

dfs(t->end);

}

t=t->next;

}

}

}

int inqueue(int a)

{

queue[tail++]=a;

return 0;

}

int dequeue()

{

if (front == tail)

return -987654321;

return queue[front++];

}

#include <stdio.h>

#include <stdlib.h>

#include <memory.h>

struct node

{

int end;

int flow;

int cap;

struct node* next;

struct node* pair;

};

typedef struct node node;

int queue[1000];

int front;

int tail;

int pd[1000];

int pb[1000];

int visited[1000];

struct node* adj;

int v,e;

int n;

char map[100][100];

node* insert_adj(int a, int b, int w,int c);

void dfs(int i);

int bfs(int i);

int inqueue(int a);

int dequeue();

int main(void)

{

int i,sum=0,j;

int num=0;

int startpoint;

struct node *temp1,*temp2;

FILE* fin = fopen("escape_input8.txt","r");

node* t;

//fscanf (fin,"%d %d",&v,&e);

if (fin==NULL){

printf ("파일이없음\n");

exit(0);

}

fscanf (fin,"%d",&n);

v=n*n*2;

adj = (node*)malloc(sizeof(node)*(v+3));

//adj = (node*)malloc(sizeof(node)*(n*n*2+2));

for (i=0;i<=v+2;i++){

adj[i].end=-1;

adj[i].flow=0;

adj[i].cap=0;

adj[i].next=NULL;

}

for (i=0;i<n;i++)

fscanf (fin,"%s",map[i]);

num=1;

startpoint=0;

for (i=0;i<n;i++)

{

for (j=0;j<n;j++)

{

if (map[i][j] == '1')//start

{

temp1=insert_adj(0,num,0,1);

temp2=insert_adj(num,0,0,0);

temp1->pair = temp2;

temp2->pair = temp1;

startpoint++;

}

if (i!=0)//위쪽연결

{

temp1=insert_adj(num+1,num-2*n,0,1);

temp2=insert_adj(num-2*n,num+1,0,0);

temp1->pair = temp2;

temp2->pair = temp1;

}

if (i != n-1) // 아래쪽연결

{

temp1=insert_adj(num+1,num+2*n,0,1);

temp2=insert_adj(num+2*n,num+1,0,0);

temp1->pair = temp2;

temp2->pair = temp1;

}

if (j != 0) // 왼쪽연결

{

temp1=insert_adj(num+1,num-2,0,1);

temp2=insert_adj(num-2,num+1,0,0);

temp1->pair = temp2;

temp2->pair = temp1;

}

if (j!=n-1)// 오른쪽연결

{//problem

temp1=insert_adj(num+1,num+2,0,1);

temp2=insert_adj(num+2,num+1,0,0);

temp1->pair = temp2;

temp2->pair = temp1;

}

//innode -> outnode

temp1=insert_adj(num,num+1,0,1);

temp2=insert_adj(num+1,num,0,0);

temp1->pair = temp2;

temp2->pair = temp1;

if (i==0 || i == n-1 || j == 0 || j == n-1) // end

{

temp1=insert_adj(num+1,n*n*2+1,0,1);

temp2=insert_adj(n*n*2+1,num+1,0,0);

temp1->pair = temp2;

temp2->pair = temp1;

}

num+=2;

}

}

/*

for (i=0;i<e;i++)

{

struct node *temp1,*temp2;

fscanf (fin,"%d %d %d",&a,&b,&c);

temp1=insert_adj(a,b,0,c);

temp2=insert_adj(b,a,0,0);

temp1->pair = temp2;

temp2->pair = temp1;

//insert_adj(b,a,w);

}

*/

memset(visited,-1,sizeof(visited));

memset(pd,-1,sizeof(pd));

memset(pb,-1,sizeof(pb));

memset(visited,-1,sizeof(visited));

/*

for (int i=0;i<v;i++)

{

node* t=&adj[i];

while(t!=NULL)

{

printf ("<%d %d %d (%d)> ",i,t->end,t->cap,t->pair->cap);

t=t->next;

}

printf ("\n");

}

*/

while(1)

{

int minflow;

memset(visited,-1,sizeof(visited));

memset(queue,0,sizeof(queue));

front=tail=0;

inqueue(0);

minflow=bfs(0);

printf ("minflow : %d \n\n",minflow);

if ( visited[v+1] == -1 )

break;

else

{

int child = v+1;

int parent = pb[child];

node* t=&adj[child];

while (parent != 0)

{

t=&adj[parent];

while(t!=NULL){

if (t->end == child)

break;

t=t->next;}

t->flow += minflow;

t->pair->flow += -minflow;

child=parent;

parent = pb[child];

}

/*

while(t!=NULL){

if (t->end == parent)

break;

t=t->next;}

t->flow += -minflow;

t->pair->flow += +minflow;

*/

t=&adj[0];

while(t!=NULL){

if (t->end == child)

break;

t=t->next;}

t->flow += minflow;

t->pair->flow += -minflow;

}

}

node* temp = &adj[v+1];

while (temp!= NULL)

{

sum += temp->pair->flow;

temp = temp->next;

}

printf ("start : %d\n",startpoint);

printf ("sum : %d\n",sum);

if (startpoint == sum)

printf ("escape success\n");

else

printf ("escape fail\n");

return 0;

}

node* insert_adj(int a, int b, int w,int c){

node* temp;

node* z;

if (adj[a].end == -1){

adj[a].end=b;

adj[a].flow=w;

adj[a].cap=c;

adj[a].next=NULL;

return &adj[a];

}

temp=&adj[a];

while(temp->next != NULL)

{

if (temp->end == b)

{

temp->cap=c;

return temp;

}

temp=temp->next;

}

if (temp->end == b)

{

temp->cap=c;

return temp;

}

z = (node*)malloc(sizeof(node));

z->end=b;

z->flow=w;

z->cap=c;

z->next=NULL;

temp->next=z;

return z;

}

int bfs(int i)

{

int z = dequeue();

int min=987654321;

while( z!=-987654321)

{

node* t = &adj[z];

while(t!=NULL &&t->end != -1)

{

if (t->cap-t->flow > 0 && visited[t->end] == -1)

{

//printf ("%d %d\n",t->end,t->cap - t->flow);

if (t->cap - t->flow <min)

min=t->cap-t->flow;

if (t->end == v+1){

visited[t->end] = 1;

pb[t->end]=z;

return min;

}

visited[t->end] = 0;

pb[t->end] = z;

inqueue(t->end);

}

t=t->next;

}

visited[z] = 1;

z=dequeue();

}

return min;

}

void dfs(int i)

{

if (visited[i] != -1)

return;

else

{

node* t=&adj[i];

visited[i]=1;

while( t!=NULL &&t->end != -1 )

{

if (visited[t->end] == -1){

pd[t->end]=i;

dfs(t->end);

}

t=t->next;

}

}

}

int inqueue(int a)

{

queue[tail++]=a;

return 0;

}

int dequeue()

{

if (front == tail)

return -987654321;

return queue[front++];

}

input 1

20 51

0 1 36

0 2 24

0 3 41

0 8 13

1 4 15

1 5 14

1 6 9

1 10 3

2 5 14

2 8 8

2 11 9

3 6 20

3 7 13

3 11 9

4 9 6

4 12 10

5 6 6

5 9 8

5 10 12

6 10 10

6 11 4

7 16 10

7 20 13

8 15 8

8 16 15

9 12 9

9 13 13

9 21 6

10 13 4

10 14 20

11 10 7

11 14 9

11 15 30

12 17 6

12 18 4

13 17 10

13 18 6

14 18 12

14 19 16

15 16 4

15 19 23

15 20 4

16 20 14

17 18 3

17 21 7

18 19 2

18 21 11

19 20 3

19 21 20

20 19 9

20 21 14

output 1

Max Flow is 58

#include <stdio.h>

#include <stdlib.h>

#include <memory.h>

struct node

{

int end;

int flow;

int cap;

struct node* next;

struct node* pair;

};

typedef struct node node;

int queue[1000];

int front;

int tail;

int pd[100];

int pb[100];

int visited[100];

struct node* adj;

int v,e;

node* insert_adj(int a, int b, int w,int c);

void dfs(int i);

int bfs(int i);

int inqueue(int a);

int dequeue();

int main(void)

{

int i,sum=0;

int a,b,w=0,c;

FILE* fin = fopen("input2.txt","r");

node* t;

fscanf (fin,"%d %d",&v,&e);

adj = (node*)malloc(sizeof(node)*(v+2));

for (i=0;i<=v+1;i++){

adj[i].end=-1;

adj[i].flow=0;

adj[i].cap=0;

adj[i].next=NULL;

}

for (i=0;i<e;i++)

{

struct node *temp1,*temp2;

fscanf (fin,"%d %d %d",&a,&b,&c);

temp1=insert_adj(a,b,0,c);

temp2=insert_adj(b,a,0,0);

temp1->pair = temp2;

temp2->pair = temp1;

//insert_adj(b,a,w);

}

memset(visited,-1,sizeof(visited));

memset(pd,-1,sizeof(pd));

memset(pb,-1,sizeof(pb));

memset(visited,-1,sizeof(visited));

for (int i=0;i<v;i++)

{

node* t=&adj[i];

while(t!=NULL)

{

printf ("<%d %d %d (%d)> ",i,t->end,t->cap,t->pair->cap);

t=t->next;

}

printf ("\n");

}

while(1)

{

int minflow;

memset(visited,-1,sizeof(visited));

memset(queue,0,sizeof(queue));

front=tail=0;

inqueue(0);

minflow=bfs(0);

printf ("minflow : %d \n\n",minflow);

if ( visited[v+1] == -1 )

break;

else

{

int child = v+1;

int parent = pb[child];

node* t=&adj[child];

while (parent != 0)

{

t=&adj[parent];

while(t!=NULL){

if (t->end == child)

break;

t=t->next;}

t->flow += minflow;

t->pair->flow += -minflow;

child=parent;

parent = pb[child];

}

/*

while(t!=NULL){

if (t->end == parent)

break;

t=t->next;}

t->flow += -minflow;

t->pair->flow += +minflow;

*/

t=&adj[0];

while(t!=NULL){

if (t->end == child)

break;

t=t->next;}

t->flow += minflow;

t->pair->flow += -minflow;

}

}

node* temp = &adj[v+1];

while (temp!= NULL)

{

sum += temp->pair->flow;

temp = temp->next;

}

printf ("sum : %d\n",sum);

return 0;

}

node* insert_adj(int a, int b, int w,int c){

node* temp;

node* z;

if (adj[a].end == -1){

adj[a].end=b;

adj[a].flow=w;

adj[a].cap=c;

adj[a].next=NULL;

return &adj[a];}

temp=&adj[a];

while(temp->next != NULL)

{

if (temp->end == b)

{

temp->cap=c;

return temp;

}

temp=temp->next;

}

if (temp->end == b)

{

temp->cap=c;

return temp;

}

z=(node*) malloc(sizeof(node));

z->end=b;

z->flow=w;

z->cap=c;

z->next=NULL;

temp->next=z;

return z;

}

int bfs(int i)

{

int z = dequeue();

int min=987654321;

while( z!=-987654321)

{

node* t = &adj[z];

while(t!=NULL &&t->end != -1)

{

if (t->cap-t->flow > 0 && visited[t->end] == -1)

{

//printf ("%d %d\n",t->end,t->cap - t->flow);

if (t->cap - t->flow <min)

min=t->cap-t->flow;

if (t->end == v+1){

visited[t->end] = 1;

pb[t->end]=z;

return min;

}

visited[t->end] = 0;

pb[t->end] = z;

inqueue(t->end);

}

t=t->next;

}

visited[z] = 1;

z=dequeue();

}

return min;

}

void dfs(int i)

{

if (visited[i] != -1)

return;

else

{

node* t=&adj[i];

visited[i]=1;

while( t!=NULL &&t->end != -1 )

{

if (visited[t->end] == -1){

pd[t->end]=i;

dfs(t->end);

}

t=t->next;

}

}

}

int inqueue(int a)

{

queue[tail++]=a;

return 0;

}

int dequeue()

{

if (front == tail)

return -987654321;

return queue[front++];

}

#include <stdio.h>

#include <stdlib.h>

#include <memory.h>

struct node

{

int w;

int end;

struct node* next;

};

typedef struct node node;

struct heapnode

{

int end;

int val;

};

typedef struct heapnode heapnode;

int queue[1000];

int front;

int tail;

int inqueue(int a)

{

queue[tail++]=a;

return 0;

}

int dequeue()

{

if (front == tail)

return -987654321;

return queue[front++];

}

int pd[100];

int pb[100];

int visited[100];

node* adj;

int v,e;

struct heapnode heap[10000];

int heapsize;

void insert_adj(int a, int b, int w){

node* temp;

node* z;

if (adj[a].end == 0){

adj[a].end=b;

adj[a].w=w;

adj[a].next=NULL;

return;}

temp=&adj[a];

while(temp->next != NULL){

temp=temp->next;}

z=(node*) malloc(sizeof(node));

z->end=b;

z->w=w;

z->next=NULL;

temp->next=z;

}

void dfs(int i)

{

if (visited[i] != -1)

return;

else

{

node* t=&adj[i];

visited[i]=1;

while( t!=NULL &&t->end != 0 )

{

if (visited[t->end] == -1){

pd[t->end]=i;

dfs(t->end);

}

t=t->next;

}

}

}

void bfs(int i)

{

int z = dequeue();

while( z!=-987654321)

{

node* t = &adj[z];

while(t!=NULL &&t->end != 0)

{

if (visited[ t->end] == -1)

{

visited[t->end] = 0;

pb[t->end] = z;

inqueue(t->end);

}

t=t->next;

}

visited[z] = 1;

z=dequeue();

}

}

int main(void)

{

int i,sum=0;

int a,b,w=0;

FILE* fin = fopen("input.txt","r");

node* t;

fscanf (fin,"%d %d",&v,&e);

adj = (node*)malloc(sizeof(node)*(v+1));

for (i=0;i<=v;i++){

adj[i].end=0;

adj[i].w=0;

adj[i].next=NULL;

}

for (i=0;i<e;i++)

{

fscanf (fin,"%d %d",&a,&b);

insert_adj(a,b,w);

//insert_adj(b,a,w);

}

memset(visited,-1,sizeof(visited));

memset(pd,-1,sizeof(pd));

memset(pb,-1,sizeof(pb));

for (int i=1;i<=v;i++)

{

if (visited[i]==-1)

dfs(i);

}

memset(visited,-1,sizeof(visited));

for (int i=1;i<=v;i++)

{

if (visited[i]==-1){

inqueue(i);

bfs(i);

}

}

for (i=1;i<=v;i++)

{

printf ("%d ",pd[i]);

}

printf ("\n");

for (i=1;i<=v;i++)

{

printf ("%d ",pb[i]);

}

printf ("\n");

return 0;

}