比赛 |
20120709 |
评测结果 |
TAAAAAAAAATA |
题目名称 |
聪明的推销员 |
最终得分 |
83 |
用户昵称 |
ZhouHang |
运行时间 |
3.360 s |
代码语言 |
C++ |
内存使用 |
43.52 MiB |
提交时间 |
2012-07-09 10:05:00 |
显示代码纯文本
/**
*Prob : salenet
*Data : 2012-7-9
*Sol : 骗分
*/
#include <cstdio>
#include <cstring>
#include <cmath>
#define MaxN 3010
#define oo 200000000
using namespace std;
int in[MaxN];
int n,count;
bool used[MaxN],d[MaxN][MaxN];
int a[MaxN][MaxN],mindis[MaxN];
//dfs判断存在性
void dfs(int x)
{
used[x] = true; count++;
for (int i=1; i<=n; i++)
if (d[x][i]&&!used[i]) dfs(i);
}
//寻找环,返回其中的一个点
int find_circle(int x)
{
bool v[MaxN];
memset(v,0,sizeof(v));
int t = in[x];
v[x] = true;
while (t&&!v[in[t]])
v[t] = true, t = in[t];
return t;
}
int min_tree_pic()
{
int i,j,k,u,tt,t,ans = 0;
memset(used,false,sizeof(used));
count = 0; dfs(0);
if (count<n+1) return -1;
memset(used,false,sizeof(used));
//初始in数组
for (i=1,k=0,in[0]=-1; i<=n; i++) {
for (j=0,t=oo; j<=n; j++)
if (!used[j]&&d[j][i]&&t>a[j][i]) {
t = a[j][i]; k = j;
}
in[i] = k; mindis[i] = t;
}
while (true) {
for (i=1; i<=n; i++)
if (!used[i]&&(tt=find_circle(i))) {
i = tt;
u = in[i];
ans += mindis[i];
while (u-i) {
used[u] = true;
ans += mindis[u]; u = in[u];
}
for (j=0; j<=n; j++)
if (!used[j]&&j-i)
a[j][i] -= mindis[i];
for (j=0; j<=n; j++)
if (!used[j]&&j-i) {
for (u=in[i]; u-i; u=in[u]) {
if(d[u][j]&&(a[u][j]<a[i][j]||!d[i][j])) //更新dis[i][j]
a[i][j]=a[u][j],d[i][j]=true;
if(d[j][u]&&(a[j][u]-mindis[u]<a[j][i]||!d[j][i]))//更新dis[j][i]
a[j][i]=a[j][u]-mindis[u],d[j][i]=true;
}
}
break;
}
if (i>n) break;
for(i=1,in[0]=-1;i<=n;i++)if(!used[i]) //需要重新生成in
{
for(j=0,t=oo,k=0;j<=n;j++)if(!used[j]&&d[j][i]&&t>a[j][i])
t=a[j][i],k=j;
in[i]=k;mindis[i]=t;
}
}
for(i=1;i<=n;i++)if(!used[i]) //加上最后不成环的结点的mindis值
ans+=mindis[i];
return ans;
}
int main()
{
freopen("salenet.in","r",stdin);
freopen("salenet.out","w",stdout);
int p,r,x,y,z;
scanf("%d",&n);
memset(d,false,sizeof(d));
memset(a,0,sizeof(a));
scanf("%d",&p);
for (int i=1; i<=p; i++) {
scanf("%d%d",&y,&z);
a[0][y] = z;
d[0][y] = true;
}
scanf("%d",&r);
for (int i=1; i<=r; i++) {
scanf("%d%d",&x,&y);
a[x][y] = 0; d[x][y] = true;
}
for (int i=0; i<=n; i++)
d[i][i] = 0;
int ans = min_tree_pic();
if (ans<0) {
printf("NO\n");
for (int i=1; i<=n; i++)
if (!used[i]) { printf("%d\n",i); break;}
}
else printf("YES\n%d\n",ans);
fclose(stdin); fclose(stdout);
return 0;
}