$NOIP2003$ 题解报告

 1 #include<bits/stdc++.h>
 2 #define ri register int
 3 #define ll long long
 4 #define rl register ll
 5 #define go(i,a,b) for(ri i=a;i<=b;i++)
 6 #define back(i,a,b) for(ri i=a;i>=b;i--)
 7 #define g() getchar()
 8 #define il inline
 9 #define pf printf
10 #define mem(a,b) memset(a,b,sizeof(a))
11 #define P pair<int,int>
12 #define mp make_pair
13 #define pb push_back
14 using namespace std;
15 il int fr(){
16     ri w=0,q=1;char ch=g();
17     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)q=-1;ch=g();}
18     while(ch>=‘0‘&&ch<=‘9‘)w=(w<<1)+(w<<3)+ch-‘0‘,ch=g();
19     return w*q;
20 }
21 const int N=102;
22 int n,p,u[N],c[N],du[N],num;
23 queue<int>q;
24 vector<P>w[N];
25 struct node{
26     int id,as;
27 }ans[N];
28 il bool cmp(node x,node y){return x.id<y.id;}
29 int main(){
30     //freopen(".in","r",stdin);
31     //freopen(".out","w",stdout);
32     n=fr();p=fr();
33     go(i,1,n){
34         c[i]=fr(),u[i]=fr();
35         if(c[i]>0)q.push(i);
36         else c[i]-=u[i];
37     }
38     go(i,1,p){
39         ri x=fr(),y=fr(),z=fr();
40         w[x].pb(mp(y,z));du[y]++;
41     }
42     while(!q.empty()){
43         ri p=q.front();q.pop();
44         ri siz=w[p].size();
45         //cout<<"p="<<p<<" c="<<c[p]<<endl;
46         if(siz==0&&c[p]>0)ans[++num]=(node){p,c[p]};
47         go(i,0,siz-1){
48             int to=w[p][i].first,W=w[p][i].second;
49             if(c[p]>0)c[to]+=W*c[p];du[to]--;
50             /*cout<<"to="<<to<<" c="<<c[to]<<endl;
51             cout<<"du="<<du[to]<<endl;*/
52             if(du[to]==0)q.push(to);
53         }
54     }
55     if(num==0){puts("NULL");return 0;}
56     sort(ans+1,ans+1+num,cmp);
57     go(i,1,num)pf("%d %d\n",ans[i].id,ans[i].as);
58     return 0;
59 }

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=302;
 4 int n,p,ans=300;
 5 int father[N],depth[N]={0,1},dep[N][N];
 6 bool tag[N];
 7 void build(int x,int y){
 8     if(depth[y]) swap(x,y);
 9     father[y]=x;
10     depth[y]=depth[x]+1;
11     dep[depth[y]][++dep[depth[y]][0]]=y;
12     return;
13 }
14 void dfs(int deep,int die){
15     if(die>=ans) return;
16     int num=0,d[N];
17     for(int i=1;i<=dep[deep][0];i++){
18         tag[dep[deep][i]]=1;
19         if(!tag[father[dep[deep][i]]]) d[++num]=dep[deep][i],tag[dep[deep][i]]=0;
20         else tag[dep[deep][i]]=1;
21     }
22     if(num==0){
23         ans=die;
24         return;
25     }
26     die+=num-1;
27     for(int i=1;i<=num;i++){
28         tag[d[i]]=1;
29         dfs(deep+1,die);
30         tag[d[i]]=0;
31     }
32     return;
33 }
34 int main(){
35     int x,y;
36     scanf("%d%d",&n,&p);
37     for(int i=1;i<=p;i++){
38         scanf("%d%d",&x,&y);
39         build(x,y);
40     }
41     dfs(2,1);
42     printf("%d\n",ans);
43     return 0;
44 }