求助lyt大佬快显灵！！！！！！！！！！！！！！！！！！

睿利之刃

求作业四题题解，做出来之后就往里面发！！！！！

lyt0707

1. #include <cstdio>
   
2. #include <cstring>
   
3. #include <vector>
   
4. #include <iostream>
   
5. #include <algorithm>
   
6. using namespace std;
   
7. int n,cnt,low[20009],flag[20009],num[20009],root,m,ans,gedian,book[20009],t,hahaha=0,ansx=0;
   
8. long long u;
   
9. vector <int> e[20009];
   
10. void dfs(int cur,int father)
    
11. {
    
12.     int child=0,i;
    
13.     cnt++;
    
14.     num[cur]=cnt;
    
15.     low[cur]=cnt;
    
16.     for(i=0;i<e[cur].size();i++)
    
17.     {
    
18.         int v = e[cur][i];
    
19.         if(num[v]==0)
    
20.         {
    
21.             child++;
    
22.               
    
23.             dfs(v,cur);
    
24.             low[cur] = min(low[cur],low[v]);
    
25.             if(cur!=root && low[v]>=num[cur])
    
26.             {
    
27.                 flag[cur]=1;
    
28.             }
    
29.             if(cur==root && child>=2)
    
30.             {
    
31.                 flag[cur]=1;
    
32.             }
    
33.         }
    
34.         else
    
35.         {
    
36.             if(v!=father)
    
37.             {
    
38.                 low[cur]=min(low[cur],num[v]);
    
39.             }
    
40.         }
    
41.     }
    
42.     return;
    
43. }
    
44. void use(int v)
    
45. {
    
46.     if(book[v]==t)
    
47.     {
    
48.         return;
    
49.     }
    
50.     book[v]=t;
    
51.     if(flag[v]==1)
    
52.     {
    
53.         gedian++;
    
54.         return;
    
55.     }
    
56.     ans++;
    
57.     for(int x=0;x<e[v].size();x++)
    
58.     {
    
59.         use(e[v][x]);
    
60.     }
    
61.     return;
    
62. }
    
63. int main()
    
64. {
    
65.     int i,j;
    
66.     while(scanf("%d",&m) && m!=0)
    
67.     {
    
68.       
    
69.         cnt=0;
    
70.         memset(flag,0,sizeof(flag));
    
71.         memset(book,0,sizeof(book));
    
72.         memset(low,0,sizeof(low));
    
73.         memset(num,0,sizeof(num));
    
74.         gedian=0;
    
75.         ans=0;
    
76.         t=-1;
    
77.         n=0;
    
78.         u=1;
    
79.         for(i=1;i<=m;i++)
    
80.         {
    
81.             int a,b;
    
82.             scanf("%d%d",&a,&b);
    
83.             n=max(a,n);
    
84.             n=max(b,n);
    
85.             e[a].push_back(b);
    
86.             e[b].push_back(a);
    
87.         }
    
88.         for(i=1;i<=n;i++)
    
89.         {
    
90.             if(num[i]==0)
    
91.             {
    
92.                 root=i;
    
93.                 dfs(root,root);
    
94.             }
    
95.         }
    
96.         u=1;
    
97.         for(i=1;i<=n;i++)
    
98.         {
    
99.             if(book[i]==0 && flag[i]!=1)
    
100.             {
     
101.                 use(i);
     
102.                 t--;
     
103.                 if(gedian==1)
     
104.                 {
     
105.                     ansx++;
     
106.                     u=u*ans;
     
107.                 }
     
108.                 ans=0;
     
109.                 gedian=0;
     
110.             }
     
111.         }
     
112.         hahaha++;
     
113.         int h;
     
114.         h=n*(n-1)/2;
     
115.         if(ansx==0)
     
116.         {
     
117.             printf("Case %d: 2 %d\n",hahaha,h);
     
118.         }
     
119.         else
     
120.         {
     
121.             printf("Case %d: %d %lld\n",hahaha,ansx,u);
     
122.         }
     
123.          
     
124.         ansx=0;
     
125.         for(i=1;i<=n;i++)
     
126.         {
     
127.             e[i].clear();
     
128.         }
     
129.     }
     
130.     return 0;
     
131. }

复制代码

lyt0707

游览农场

1. #include<cstdio>
   
2. 
   
3. using namespace std;
   
4. 
   
5. struct node
   
6. {
   
7.     int s;
   
8.     int e;
   
9.     int f;
   
10.     int c;
    
11. };
    
12. 
    
13. struct node edge[30000];
    
14. int n,m,sum,inf=999999999;
    
15. int book[30000],dis[1001],father[1001];
    
16. 
    
17. 
    
18. int bellman()
    
19. {
    
20.     int i,k;
    
21.      
    
22.     for(i=0;i<=n+1;i++)
    
23.     {
    
24.         father[i]=-1;
    
25.         dis[i]=inf;
    
26.     }
    
27.      
    
28.     dis[0]=0;
    
29.     for(k=0;k<=n+1;k++)
    
30.         for(i=1;i<=m;i++)
    
31.         {
    
32.             if(edge[i].c==0) continue;
    
33.             if(dis[edge[i].e]>dis[edge[i].s]+edge[i].f)
    
34.             {
    
35.                 dis[edge[i].e]=dis[edge[i].s]+edge[i].f;
    
36.                 father[edge[i].e]=i;
    
37.             }
    
38.         }
    
39.     if(dis[n+1]==inf) return 0;
    
40.     return 1;
    
41. }
    
42. 
    
43. void dfs()
    
44. {
    
45.     int u,x,i;
    
46.      
    
47.     while(bellman())
    
48.     {
    
49.         u=n+1;
    
50.         while(father[u]!=-1)
    
51.         {
    
52.             x=father[u];
    
53.             if(x<=m-4)
    
54.             {
    
55.                 edge[x].c=0;
    
56.                 edge[book[x]].f=-1;
    
57.             }
    
58.             else
    
59.             {
    
60.                 edge[x].c-=1;
    
61.                 edge[book[x]].c+=1;
    
62.             }
    
63.             u=edge[x].s;
    
64.         }
    
65.         sum+=dis[n+1];
    
66.     }
    
67.     return ;
    
68. }
    
69.                  
    
70. 
    
71. int main()
    
72. {
    
73.     int i,t1,t2,t3;
    
74.      
    
75.     scanf("%d%d",&n,&m);
    
76.     for(i=1;i<=m;i++)
    
77.     {
    
78.         scanf("%d%d%d",&t1,&t2,&t3);
    
79.         edge[i].s=t1;
    
80.         edge[i].e=t2;
    
81.         edge[i].f=t3;
    
82.         edge[i].c=1;
    
83.         book[i]=i+m;
    
84.          
    
85.         edge[i+m].s=t2;
    
86.         edge[i+m].e=t1;
    
87.         edge[i+m].f=t3;
    
88.         edge[i+m].c=1;
    
89.         book[i+m]=i;
    
90.     }
    
91.     m=m*2;
    
92.      
    
93.     edge[m+1].s=0;
    
94.     edge[m+1].e=1;
    
95.     edge[m+1].f=0;
    
96.     edge[m+1].c=2;
    
97.     book[m+1]=m+2;
    
98.      
    
99.     edge[m+2].s=1;
    
100.     edge[m+2].e=0;
     
101.     edge[m+2].f=0;
     
102.     edge[m+2].c=0;
     
103.     book[m+2]=m+1;
     
104.      
     
105.     edge[m+3].s=n;
     
106.     edge[m+3].e=n+1;
     
107.     edge[m+3].f=0;
     
108.     edge[m+3].c=2;
     
109.     book[m+3]=m+4;
     
110. 
     
111.     edge[m+4].s=n+1;
     
112.     edge[m+4].e=n;
     
113.     edge[m+4].f=0;
     
114.     edge[m+4].c=0;
     
115.     book[m+4]=m+3;
     
116.      
     
117.     m=m+4;
     
118.      
     
119.      
     
120.     dfs();
     
121.      
     
122.     printf("%d",sum);
     
123.      
     
124.     return 0;
     
125. }

复制代码

Forinser

lyt0707 发表于 2019-1-29 17:29
游览农场

bellman+DFS吗？做出来倒是挺妙的