fork download
  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.  
  164. public Scanner(InputStream s) {
  165. }
  166.  
  167. public Scanner(FileReader s) {
  168. br = new BufferedReader(s);
  169. }
  170.  
  171. public String next() throws IOException {
  172. while (st == null || !st.hasMoreTokens())
  173. st = new StringTokenizer(br.readLine());
  174. return st.nextToken();
  175. }
  176.  
  177. public int nextInt() throws IOException {
  178. return Integer.parseInt(next());
  179. }
  180.  
  181. public long nextLong() throws IOException {
  182. return Long.parseLong(next());
  183. }
  184.  
  185. public String nextLine() throws IOException {
  186. return br.readLine();
  187. }
  188. public boolean ready() throws IOException {return br.ready();}
  189. public double nextDouble() throws IOException {return Double.parseDouble(next());}
  190.  
  191. }
  192.  
  193. }
Success #stdin #stdout 0.06s 2184192KB
stdin
6
2
1 4
4 6
010000
001000
000100
000010
000001
000000
stdout
YES
5
1 2
2 3
3 4
4 5
5 6