RCC 2014 Warmup (Div. 1)

暴力

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<stdlib.h>
 6 #include<vector>
 7 #include<cmath>
 8 #include<queue>
 9 #include<set>
10 using namespace std;
11 #define N 1010
12 #define LL long long
13 #define INF 0xfffffff
14 const double eps = 1e-8;
15 const double pi = acos(-1.0);
16 const double inf = ~0u>>2;
17 vector<int>ed[N];
18 bool w[N][N];
19 int main()
20 {
21     int i,j,n,m;
22     int flag = 1;
23     cin>>n>>m;
24     for(i = 1; i <=  n;i++)
25     {
26         int k = 0;
27         w[i][i] = 1;
28         for(j = 1 ; j <= n ; j++)
29         {
30             if(!w[i][j])
31             {
32                 w[i][j] = 1;
33                 w[j][i] = 1;
34                 ed[i].push_back(j);
35                 k++;
36             }
37             if(k==m) break;
38         }
39         if(k<m)
40         {
41             flag = 0;
42             break;
43         }
44     }
45     if(!flag) {puts("-1");return 0;}
46     printf("%d
",n*m);
47     for(i = 1; i <= n ;i++)
48     {
49         for(j = 0; j < ed[i].size(); j++)
50         printf("%d %d
",i,ed[i][j]);
51     }
52     return 0;
53 }

View Code

B 状压

这个需要排下序，不然不能保证压的正确。

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<stdlib.h>
 6 #include<vector>
 7 #include<cmath>
 8 #include<queue>
 9 #include<set>
10 using namespace std;
11 #define N 1010
12 #define LL long long
13 //#define INF 1e18+1e12
14 const double eps = 1e-8;
15 const double pi = acos(-1.0);
16 const double inf = ~0u>>2;
17 const LL INF = (1ll<<62);
18 LL dp[1<<20];
19 struct node
20 {
21     int x,k,m;
22     int a[105];
23     int s;
24 }p[105];
25 bool cmp(node a,node b)
26 {
27     return a.k<b.k;
28 }
29 int main()
30 {
31     int i,j,n,m;
32     LL b;
33     cin>>n>>m>>b;
34     for(i = 0 ; i < (1<<m) ; i++)
35     dp[i] = INF;
36     for(i = 1; i <= n ;i++)
37     {
38         p[i].s = 0 ;
39         scanf("%d%d%d",&p[i].x,&p[i].k,&p[i].m);
40         for(j = 0; j < p[i].m ; j++)
41         {
42             scanf("%d",&p[i].a[j]);
43             p[i].s|=(1<<(p[i].a[j]-1));
44         }
45     }
46     sort(p+1,p+n+1,cmp);
47     dp[0] = 0;
48     LL ans= INF;
49     for(i = 1; i <= n ;i++)
50     {
51         for(j = 0 ;j < (1<<m) ; j++)
52         {
53             if(dp[j]==INF) continue;
54             dp[j|p[i].s] = min(dp[j|p[i].s],dp[j]+p[i].x);
55         }
56         ans = min(ans,dp[(1<<m)-1]+p[i].k*b);
57     }
58     if(ans==INF)
59     puts("-1");
60     else
61     cout<<ans<<endl;
62     return 0;
63 }

View Code