ut
3
0 1 1
1 0 1
1 1 0
output
NO
input
2
0 0
0 0
output
NO
Note
In the first example, the required tree exists. It has one edge between nodes 1 and 2 with weight 2, another edge between nodes 1 and 3 with weight 7.
In the second example, it is impossible because d1,?1 should be 0, but it is 1.
In the third example, it is impossible because d1,?2 should equal d2,?1.
#include
#include
#include
#include
using namespace std; typedef long long int LL; const int maxn=2222; int n; LL d[maxn][maxn]; int main() { scanf("%d",&n); bool flag=true; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { scanf("%I64d",&d[i][j]); if(i==j&&d[i][j]) flag=false; } } for(int i=1;i<=n&&flag;i++) for(int j=1;j<=n&&flag;j++) { if(d[i][j]!=d[j][i]) flag=false; if(i!=j&&d[i][j]==0) flag=false; } if(flag==false) { puts("NO"); return 0; } for(int i=1;i<=n&&flag;i++) { LL MINI=(1LL<<62),pos=-1; for(int j=1;j<=n;j++) { if(d[i][j]