比赛 |
20120709 |
评测结果 |
AAAWAAAAAAAW |
题目名称 |
聪明的推销员 |
最终得分 |
83 |
用户昵称 |
Citron酱 |
运行时间 |
0.027 s |
代码语言 |
C++ |
内存使用 |
0.42 MiB |
提交时间 |
2012-07-09 09:34:22 |
显示代码纯文本
#include <cstdio>
#include <climits>
#define I_F "salenet.in"
#define O_F "salenet.out"
const int MAXn=3000;
const int MAXm=8000+1;
struct edge
{
int x;
edge *next;
};
int n, p;
edge pool[MAXm];
edge *ph=pool;
edge *map[MAXn]={NULL};
int c[MAXn];
int s[MAXn];
int d[MAXn]={0}, l[MAXn]={0}, index=0;
int st[MAXn];
int top=0;
short f[MAXn];
long ans=0;
bool flag=true;
void Input();
void Tarjan(const int&);
inline int Min(const int&, const int&);
void Dfs(const int&);
void Search();
void Output();
int main()
{
Input();
Search();
Output();
return 0;
}
void Input()
{
int m, a;
edge *temp;
freopen(I_F,"r",stdin);
scanf("%d%d",&n,&p);
for (int i=0; i<n; ++i)
c[i]=INT_MAX;
for (int i=0; i<p; ++i)
{
scanf("%d",&a);
scanf("%d",&c[a-1]);
}
for (scanf("%d",&m); m>0; --m)
{
scanf("%d",&a);
temp=map[--a];
map[a]=ph++;
scanf("%d",&(map[a]->x));
--map[a]->x;
map[a]->next=temp;
}
}
void Tarjan(const int &x)
{
d[x]=l[x]=++index;
f[x]=1;
st[top++]=x;
for (edge *i=map[x]; i!=NULL; i=i->next)
if (f[i->x]==0)
{
Tarjan(i->x);
l[x]=Min(l[x],l[i->x]);
}
else if (f[i->x]==1)
l[x]=Min(l[x],d[i->x]);
if (d[x]==l[x])
{
int v;
do
{
v=st[--top];
s[v]=x;
} while (v!=x);
}
}
inline int Min(const int &a, const int &b)
{
return (a<b)?a:b;
}
void Dfs(const int &x)
{
f[x]=1;
for (edge *i=map[x]; i!=NULL; i=i->next)
if (f[i->x]==0)
Dfs(i->x);
}
void Search()
{
int m[MAXn];
for (int i=0; i<n; ++i)
f[i]=0,
s[i]=i;
for (int i=0; i<n; ++i)
if (f[i])
Tarjan(i);
for (int i=0; i<n; ++i)
f[i]=0,
m[i]=INT_MAX;
for (int i=0; i<n; ++i)
m[s[i]]=Min(m[s[i]],c[i]);
for (int i=0; i<n; ++i)
if (f[i]==0 && m[s[i]]<INT_MAX)
Dfs(i),
ans+=m[s[i]];
for (int i=0; i<n; ++i)
if (f[i]==0)
{
ans=i+1;
flag=false;
break;
}
}
void Output()
{
freopen(O_F,"w",stdout);
if (flag)
printf("YES\n%ld\n",ans);
else
printf("NO\n%ld\n",ans);
}