#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;

}