1 #include<cstdio>  2 #include<cstring>  3 #include<algorithm>  4 #pragma comment(linker, "/STACK:36777216")  5 #define mt(a,b) memset(a,b,sizeof(a))  6 using namespace std;  7 typedef __int64 LL;  8 const int M=100010;  9 struct G{ 10     struct E{ 11         int v,next; 12     }e[M<<1]; 13     int le,head[M]; 14     void init(){ 15         le=0; 16         mt(head,-1); 17     } 18     void add(int u,int v){ 19         e[le].v=v; 20         e[le].next=head[u]; 21         head[u]=le++; 22     } 23 }g; 24 int n,val[M],fa[M],dep[M],num[M],son[M],top[M],sid[M]; 25 void dfs(int u){ 26     num[u]=1; 27     son[u]=0; 28     for(int i=g.head[u];~i;i=g.e[i].next){ 29         int v=g.e[i].v; 30         if(v!=fa[u]){ 31             fa[v]=u; 32             dep[v]=dep[u]+1; 33             dfs(v); 34             if(num[son[u]]<num[v]) son[u]=v; 35             num[u]+=num[v]; 36         } 37     } 38 } 39 void get(int u,int Top){ 40     sid[u]=++n; 41     top[u]=Top; 42     if(son[u]) get(son[u],top[u]); 43     for(int i=g.head[u];~i;i=g.e[i].next){ 44         int v=g.e[i].v; 45         if(v!=fa[u]&&v!=son[u]){ 46             get(v,v); 47         } 48     } 49 } 50 LL lazy[M],ans[M]; 51 void query(){ 52     LL now=0; 53     for(int i=1;i<=n;i++){ 54         now+=lazy[i]; 55         ans[i]=now; 56     } 57 } 58 void update(int x,int y,int z){ 59     lazy[x]+=z; 60     lazy[y+1]-=z; 61 } 62 void worknode(int x,int y,int z){ 63     int tx=top[x],ty=top[y]; 64     while(tx!=ty){ 65         if(dep[tx]<dep[ty]){ 66             swap(tx,ty); 67             swap(x,y); 68         } 69         update(sid[tx],sid[x],z); 70         x=fa[tx]; 71         tx=top[x]; 72     } 73     if(dep[x]>dep[y]) swap(x,y); 74     update(sid[x],sid[y],z); 75 } 76 void workedge(int x,int y,int z){ 77     int tx=top[x],ty=top[y]; 78     while(tx!=ty){ 79         if(dep[tx]<dep[ty]){ 80             swap(tx,ty); 81             swap(x,y); 82         } 83         update(sid[tx],sid[x],z); 84         x=fa[tx]; 85         tx=top[x]; 86     } 87     if(x==y) return ; 88     if(dep[x]>dep[y]) swap(x,y); 89     update(sid[son[x]],sid[y],z); 90 } 91 struct IN{ 92     int type,u,v,w; 93 }in[M]; 94 struct EDGE{ 95     int u,v; 96 }edge[M]; 97 int main(){ 98     int t,N,m,u,v; 99     while(~scanf("%d",&t)){100         int cas=1;101         while(t--){102             scanf("%d%d",&N,&m);103             g.init();104             for(int i=0;i<N-1;i++){105                 scanf("%d%d",&u,&v);106                 g.add(u,v);107                 g.add(v,u);108                 edge[i].u=u;109                 edge[i].v=v;110             }111             n=fa[1]=dep[1]=num[0]=0;112             dfs(1);113             get(1,1);114             char op[8];115             for(int i=0;i<m;i++){116                 scanf("%s%d%d%d",op,&in[i].u,&in[i].v,&in[i].w);117                 if(op[3]==‘1‘) in[i].type=1;118                 else           in[i].type=2;119             }120             mt(lazy,0);121             for(int i=0;i<m;i++){122                 if(in[i].type&1) worknode(in[i].u,in[i].v,in[i].w);123             }124             printf("Case #%d:\n",cas++);125             query();126             for(int i=1;i<=N;i++){127                 if(i>1) printf(" ");128                 printf("%I64d",ans[sid[i]]);129             }130             puts("");131             mt(lazy,0);132             for(int i=0;i<m;i++){133                 if(in[i].type==2) workedge(in[i].u,in[i].v,in[i].w);134             }135             query();136             for(int i=0;i<N-1;i++){137                 int u=edge[i].u;138                 int v=edge[i].v;139                 if(dep[u]<dep[v]){140                     swap(u,v);141                 }142                 if(i) printf(" ");143                 printf("%I64d",ans[sid[u]]);144             }145             puts("");146         }147     }148     return 0;149 }

 1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define mt(a,b) memset(a,b,sizeof(a)) 5 using namespace std; 6 double a[16][1024],dp[1<<10]; 7 int one(int x){ 8     int res=0; 9     while(x){10         if(x&1) res++;11         x>>=1;12     }13     return res;14 }15 int main(){16     int t,n,m;17     while(~scanf("%d",&t)){18         int cas=1;19         while(t--){20             scanf("%d%d",&n,&m);21             for(int i=0;i<n;i++){22                 for(int j=0;j<m;j++){23                     scanf("%lf",&a[i][j]);24                 }25             }26             int s=0,num,all=1<<n;27             bool flag=true;28             double ans=0;29             while(flag){30                 flag=false;31                 if(s+n<m){32                     flag=true;33                     num=n;34                 }35                 else{36                     num=m-s;37                 }38                 mt(dp,0);39                 for(int i=0;i<all;i++){40                     int yi=one(i);41                     if(yi>=num) continue;42                     for(int j=0;j<n;j++){43                         if((i>>j)&1) continue;44                         int next=i|(1<<j);45                         dp[next]=max(dp[next],dp[i]+a[j][s+yi]);46                     }47                 }48                 double big=0;49                 if(num==n){50                     big=dp[all-1];51                 }52                 else{53                     for(int i=0;i<all;i++){54                         if(one(i)==num){55                             big=max(big,dp[i]);56                         }57                     }58                 }59                 ans+=big;60                 s+=n;61             }62             printf("Case #%d: %.5f\n",cas++,ans);63         }64     }65     return 0;66 }