百度NOIP吧编程挑战赛第二题 Special Judge 程序下载

 
#include <iostream>
#include <string>
#include <string.h>
#include <cstdio>
#include <algorithm>
#include <fstream>
 
using namespace std;
 
bool bi[1005],map[1005][1005];
int read[1005][2];
int n,d1;
int bc[1100][1100];
const int ans[10]={25,134,179,429,499,579,649,700,799,998};
const int maxn[10]={11,101,200,500,600,700,800,900,1000,1000};
 
void dfs(int k){
    bi[k]=false;
    for (int i=1;i<=d1;++i)
     if (bi[i]&&map[k][i]) dfs(i);
}
 
int main(int argc, char *argv[])
{
	ofstream fout("score.log");
	ofstream rep("report.log");
 
	int d2, s1 ,now,p1,p2;
	freopen("contact.in","r",stdin);
 
    scanf("%d",&d1);
    ++d1;
	memset(map,false,sizeof(map));
    for (int i=1;i<=d1;++i)
     for (int j=1;j<=d1;++j)
	 {
      scanf("%d",&bc[i][j]);
	 }
	scanf("%d",&d2);
	for (int i=1;i<=d2;++i){
      scanf("%d%d",&p1,&p2);
      map[p1][p2]=map[p2][p1]=true;
    }
 
	for (int i=0;i<=9;++i) 
     if (d1==maxn[i]) now=i;
    if (d1==1000&&d2!=2) now=8;
 
//	ifstream sc(argv[2]);//"contact.out");
    freopen("contact.out","r",stdin);
 
	cin >> s1;
 
	if (s1!=ans[now]){
		fout << "0" << endl;
		rep << "the answer you give:" << s1 << endl;
		rep << "it should be:" << ans[now] << endl;
		return 0;
	}
	int m=0;
	n=1;
 
    while (cin >> read[n][0] >> read[n][1]){
      ++n;
      m+=bc[read[n-1][0]][read[n-1][1]];
      map[read[n-1][0]][read[n-1][1]]=map[read[n-1][1]][read[n-1][0]]=true;
    }
    --n;
 
    if (m!=ans[now]){
      fout << "0" << endl;
      rep << "the cost you give:" << m << endl;
      rep << "the cost should be:" << ans[now] << endl;
      return 0;
    }
 
    memset(bi,true,sizeof(bi));
    dfs(1);
    for (int i=1;i<=d1;++i)
     if (bi[i]){
       fout << "0" << endl;
       rep << "you gived edge is not a tree" << endl;
       return 0;
     }
 
	fout << "10" << endl;
	return 0;
}