fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. class Ideone {
  8.   public static int flows[][]=new int[300][300];
  9.   public static int maxFlow(int[][] cap, int s, int t) {
  10.     for (int flow = 0;;) {
  11.       int df = findPath(cap, new boolean[cap.length], s, t, Integer.MAX_VALUE);
  12.       if (df == 0)
  13.         return flow;
  14.       flow += df;
  15.     }
  16.   }
  17.  
  18.   static int findPath(int[][] cap, boolean[] vis, int u, int t, int f) {
  19.     if (u == t)
  20.       return f;
  21.     vis[u] = true;
  22.     for (int v = 0; v < vis.length; v++)
  23.       if (!vis[v] && cap[u][v] > 0) {
  24.         int df = findPath(cap, vis, v, t, Math.min(f, cap[u][v]));
  25.         if (df > 0) {
  26.           cap[u][v] -= df;
  27.           flows[u][v]+=df;
  28.           flows[v][u]-=df;
  29.           cap[v][u] += df;
  30.           return df;
  31.         }
  32.       }
  33.     return 0;
  34.   }
  35.  
  36.   // Usage example
  37.   public static void main(String[] args) {
  38.     int A=0,B=0;
  39.     Scanner in = new Scanner(System.in);
  40. 	int[][] multi = new int[300][300];
  41. 	for(int i = 0; i <300; i++)
  42. 		for(int j=0; j<300; j++)
  43. 			multi[i][j]=-1;
  44. 	int n = in.nextInt();
  45. 	int m = in.nextInt();
  46. 	for(int i=0; i<n; ++i)
  47. 	{
  48. 		int a = in.nextInt();
  49. 		multi[2*n+1][i+1]=a;
  50. 		A+=a;
  51. 	}
  52. 	for(int i=0; i<n; ++i)
  53. 	{
  54. 		int b = in.nextInt();
  55. 		multi[n+i+1][2*n+2]=b;
  56. 		B+=b;
  57. 	}
  58. 	for(int i=1; i<=n; ++i)
  59. 	{
  60. 		multi[n+i][i]=100000000;
  61. 		multi[i][n+i]=100000000;
  62. 	}
  63. 	for(int i=0; i<m; ++i)
  64. 	{
  65. 		int a = in.nextInt();
  66. 		int b = in.nextInt();
  67. 		multi[a][n+b]=1000000000;
  68. 		multi[n+a][b]=1000000000;
  69. 		multi[n+b][a]=1000000000;
  70. 		multi[b][n+a]=1000000000;
  71. 	}
  72. 	int ans=maxFlow(multi, 2*n+1, 2*n+2);
  73. 	if(ans!=A || ans!=B)
  74. 		System.out.println("NO");
  75. 	else
  76. 	{
  77. 		System.out.println("YES"+n);
  78. 		for(int i=1; i<=n; ++i)
  79. 		{
  80. 			String st = "";
  81. 			for(int j=n+1; j<=2*n; ++j)
  82. 			{
  83. 				if(multi[i][j]>0)
  84. 					st=st+flows[i][j]+" ";
  85. 				else
  86. 					st=st+"0 ";
  87. 			}
  88. 			System.out.println(st);
  89. 		}
  90. 	}
  91.   }
  92. }
Success #stdin #stdout 0.1s 380608KB
comments (?)
stdin
copy 
4 4
1 2 6 3
3 5 3 1
1 2
2 3
3 4
4 2
stdout
copy 
YES4
3 -2 0 0 
0 1 1 0 
0 3 3 0 
0 3 -1 1
https://ideone.com/bGtOyZ
language:
Java (12.0.1)
created:
8 years ago
visibility:
public

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!