涛涛的Party

Time Limit : 3000/1000ms (Java/Other)   Memory Limit : 65535/32768K (Java/Other)

Total Submission(s) : 25   Accepted Submission(s) : 12

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

涛神因为极强，并且特别帅，所以拥有很多美女的联系方式，每个美女都有自己的食量以及魅力值，大家都知道，物以类聚，人以群分，朋友的朋友就是自己的朋友，所以美女一般都是有自己的美女朋友圈，而且这些美女特别团结，如果她的朋友有没有被邀请的她就不会答应邀请。涛涛想办一个party，但是他只准备了w kg的食物，他想获得最大的美女魅力值，不知道怎么邀请美女，于是他去问你，你能告诉他，他能获得的美女魅力数是多少吗

Input

数据有多组，第一行输入n,m和w(1≤n≤1000,0≤m≤min(n*(n-1)/2,10^5),1≤w≤1000)；第二行输入n个整型变量w1,w2,...,wn(1≤wi≤1000)代表美女i的食量；第三行输入n个整型变量b1,b2,...,bn(1≤bi≤106)代表美女i的魅力值；接下来的m行输入两个数x和y(1≤xi,yi≤n,xi≠yi),代表x和y是朋友

Output

输出涛涛能获得的最大魅力值

Sample Input

3 1 53 2 52 4 21 24 2 112 4 6 66 4 2 11 22 3

Sample Output

61 01背包问题和dfs加个邻接表; 用直接代码了;

1 #include 
      
        //1004 2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #define M 1005 7 using namespace std; 8  9 struct Node{10     int a,b;11 }node[M];12 int dp[M];13 vector
           
             v[M];14 stack
            
              s1,s2;15 Node eat[M];16 int ap[M];17 18 void dfs(int i){19 ap[i]=1;20 s1.push(node[i].a);21 s2.push(node[i].b);22 for(int k=0;k
             
              =eat[i].a;j--){58 dp[j]=max(dp[j],dp[j-eat[i].a]+eat[i].b );59 }60 }61 printf("%d\n",dp[w]);62 for(int i=1;i<=n;i++)63 v[i].clear();64 memset(ap,0,sizeof(ap));65 memset(dp,0,sizeof(dp));66 }67 return 0;68 }