fork download
copy 
  1. import java.util.*;
  2. import java.io.*;
  3. class D{
  4.  
  5. 	static int []p,res[];
  6. 	static int S,T,f,nodes;
  7. 	static int INF=(int)1e9;
  8. 	static PrintWriter out;
  9. 	static StringBuilder sb;
  10. 	static void augment(int u,int minEdge)
  11. 	{
  12.  
  13. 		if(u==S) 
  14. 		{
  15. 			f= minEdge;
  16. 			return;
  17. 		}
  18.  
  19. 		int v=p[u];
  20.  
  21. 		if(v!=-1)
  22. 		{
  23. 			augment(v,Math.min(minEdge, res[v][u]));
  24.  
  25. 			res[u][v]+=f;
  26. 			res[v][u] -= f;
  27.  
  28. 		}
  29.  
  30. 	}
  31. 	static int print(int u)
  32. 	{
  33.  
  34.  
  35. 		if(u==T)
  36. 			return 0;
  37. 		int ans=0;
  38. 		for(int v=0;v<nodes;v++)
  39. 			if(p[u]==v)
  40. 			{
  41.  
  42. 				if(v!=T && u!=S) {
  43. 					sb.append(u+" "+v+"\n");
  44. 					ans++;
  45. 				}
  46.  
  47. 				ans+=print(v);
  48.  
  49. 				res[v][u]--;
  50. 				break;
  51. 			}
  52. 		return ans;
  53. 	}
  54.  
  55. 	public static void main(String[] args) throws IOException 
  56. 	{
  57.  
  58. 		Scanner sc=new Scanner(System.in);
  59. 		out = new PrintWriter (System.out);
  60. 		int n=sc.nextInt();
  61. 		int k=sc.nextInt();
  62. 		nodes=n+2;
  63. 		res=new int [nodes][nodes];
  64. 		char [][]s=new char [n][n];
  65. 		int []b=new int [k];
  66. 		S=0;
  67. 		T=nodes-1;
  68. 		for(int i=0;i<k;i++)
  69. 			res[S][sc.nextInt()]=1;
  70. 		for(int i=0;i<k;i++)
  71. 		{
  72. 			int x=sc.nextInt();
  73. 			res[x][T]=1;
  74. 			b[i]=x;
  75. 		}
  76. 		for(int i=1;i<=n;i++)
  77. 		{
  78. 			s[i-1]=sc.next().toCharArray();
  79. 			for(int j=1;j<=n;j++)
  80. 				if(s[i-1][j-1]=='1')
  81. 					res[i][j]=1;
  82. 		}
  83.  
  84. 		p=new int [nodes];
  85. 		int mf=0;
  86. 		while(true)
  87. 		{
  88. 			int []dist=new int [nodes];
  89. 			f=0;
  90. 			Arrays.fill(dist, -1);
  91. 			Arrays.fill(p, -1);
  92. 			dist[S]=0;
  93. 			Queue<Integer> q= new LinkedList();
  94. 			q.add(S);
  95. 			while(!q.isEmpty())
  96. 			{
  97. 				int u=q.poll();
  98. 				if(u==T)
  99. 					break;
  100. 				for(int v=0;v<nodes;v++)
  101. 					if(dist[v]==-1 && res[u][v]>0)
  102. 					{
  103. 						dist[v]=dist[u]+1;
  104. 						p[v]=u;
  105. 						q.add(v);
  106. 					}
  107. 			}
  108.  
  109. 			augment(T, INF);
  110.  
  111.  
  112. 			if(f==0)
  113. 				break;
  114. 			else 
  115.  
  116. 				mf+=f;
  117.  
  118.  
  119. 		}
  120.  
  121. 		if(mf<k)
  122. 			out.println("NO");
  123. 		else
  124. 		{
  125. 			sb=new StringBuilder();
  126. 			out.println("YES");
  127. 			int ans=0;
  128. 			while(k-->0)
  129. 			{
  130.  
  131.  
  132. 				Queue<Integer> q=new LinkedList();
  133. 				q.add(T);
  134. 				int []dist=new int [nodes];
  135. 				p=new int[nodes];
  136. 				Arrays.fill(dist, -1);
  137. 				dist[T]=0;
  138. 				while(!q.isEmpty())
  139. 				{
  140. 					int u=q.poll();
  141. 					for(int v=0;v<nodes;v++)
  142. 						if(res[u][v]>0 && dist[v]==-1)
  143. 						{
  144. 							q.add(v);
  145. 							p[v]=u;
  146. 							dist[v]=dist[u]+1;
  147. 						}
  148. 				}
  149. 				ans+=print(S);
  150. 			}
  151. 			out.println(ans);
  152. 			out.println(sb);
  153. 		}
  154.  
  155.  
  156. 		out.close();
  157.  
  158. 	}
  159.  
  160.  
  161.  
  162. 	static class Scanner {
  163.         StringTokenizer st;
  164.         BufferedReader br;
  165.  
  166.         public Scanner(InputStream s) {
  167.             br = new BufferedReader(new InputStreamReader(s));
  168.         }
  169.  
  170.         public Scanner(FileReader s) {
  171.             br = new BufferedReader(s);
  172.         }
  173.  
  174.         public String next() throws IOException {
  175.             while (st == null || !st.hasMoreTokens())
  176.                 st = new StringTokenizer(br.readLine());
  177.             return st.nextToken();
  178.         }
  179.  
  180.         public int nextInt() throws IOException {
  181.             return Integer.parseInt(next());
  182.         }
  183.  
  184.         public long nextLong() throws IOException {
  185.             return Long.parseLong(next());
  186.         }
  187.  
  188.         public String nextLine() throws IOException {
  189.             return br.readLine();
  190.         }
  191.         public boolean ready() throws IOException {return br.ready();}
  192.         public double nextDouble() throws IOException {return Double.parseDouble(next());}
  193.  
  194.     }
  195.  
  196. }
Success #stdin #stdout 0.06s 2184192KB
comments (?)
stdin
copy 
6
2
1 4
4 6
010000
001000
000100
000010
000001
000000
stdout
copy 
YES
5
1 2
2 3
3 4
4 5
5 6
https://ideone.com/U4EjyO
language:
Java (HotSpot 12)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!