01分数规划（网络流）+状压DP+树形DP
官方题解地址：http://pan.baidu.com/s/1mg5S5z6
A
好神啊= =第一次写01分数规划
其实分数规划是要求$$ Maximize/Minimize \ \ L=\frac{A(x)}{B(x)}$$
这里我们拿最大来举例吧……因为本题就是最大嘛~
通用解法是：二分= =
假设最优解为$\lambda^*$，那么有$$\lambda^*=f(x^*)=\frac{A(x^*)}{B(x^*)} \\ \Rightarrow \lambda^* *B(x^*)=A(x^*) \\ \Rightarrow 0=A(x^*)-\lambda^* *B(x^*) $$
那么我们由上面的形式构造一个新函数$g(\lambda)$：$$g(\lambda)=max_{x \in S} \{A(x)-\lambda*B(x)\}$$
这个函数是有单调性的……我就不证明了……重点是后面的部分：
$$ \lambda<\lambda^* \Rightarrow \lambda<\frac{A(x^*)}{B(x^*)} \Rightarrow A(x^*)-\lambda *B(x^*) >0 \\ \lambda>\lambda^* \Rightarrow \lambda>\frac{A(x^*)}{B(x^*)} \Rightarrow A(x^*)-\lambda *B(x^*) <0 $$
所以我们得到这样一个定理(重要)：$$\begin{cases} g( \lambda )=0 & \Leftrightarrow & \lambda = \lambda^* \\ g( \lambda )<0 & \Leftrightarrow & \lambda < \lambda^* \\ g( \lambda )>0 & \Leftrightarrow & \lambda > \lambda^* \end{cases} $$
这题里面，$A(x)$就是边权和，$\lambda*B(x)$就是选这些点的代价啦。
那么很明显对于一个已知的$\lambda$（收益比），我们可以用最大权闭合图的模型来求出$g(\lambda)$，（因为是最大！）从而得知我们二分的这个答案$\lambda$是偏大还是偏小了……
这玩意是不是叫点边均带权的最大密度子图啊QAQ
然而这题有个细节要注意，因为我们用的是最大权闭合图，这里的边权又比较特殊……所以不会出现$g(\lambda)<0$的情况，（那种时候会变成=0），所以我们应该是在>0的时候令L=mid；else R=mid;
而我一开始是反过来写的……所以就跪了TAT 后来我灵（nao）机（zi）一（yi）动（chou），将ans<0改成了ans<eps……这就将<=0的情况都包括进去了→_→顺利出解。
事实上考试时我这题只有暴力分= =因为我数组开！小！了！……一开始定数组大小的时候没想出来正解……所以是直接按点数和边数开的……但是如果是网络流的话，点数应该是$n+m$，边数会是$n+3m$……（没算源汇）QAQTAT
//Round4 A
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
typedef long long LL;
inline int getint(){
int r=,v=; char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if (ch=='-') r=-;
for(; isdigit(ch);ch=getchar()) v=v*-''+ch;
return r*v;
}
const int N=,M=;
const double eps=1e-,INF=1e10;
/*******************template********************/ int n,m,u[M],v[M];
double p[M],ans,c[N];
struct edge{int to;double v;};
struct Net{
edge E[M];
int head[N],nxt[M<<],cnt;
void ins(int x,int y,double v){
E[++cnt]=(edge){y,v}; nxt[cnt]=head[x]; head[x]=cnt;
}
void add(int x,int y,double v){
ins(x,y,v); ins(y,x,);
}
int S,T,cur[N],d[N];
queue<int>Q;
bool mklevel(){
memset(d,-,sizeof d);
d[S]=;
Q.push(S);
while(!Q.empty()){
int x=Q.front(); Q.pop();
for(int i=head[x];i;i=nxt[i])
if (d[E[i].to]==- && E[i].v>){
d[E[i].to]=d[x]+;
Q.push(E[i].to);
}
}
return d[T]!=-;
}
double dfs(int x,double a){
if (x==T) return a;
double flow=0.0;
for(int &i=cur[x];i && a-flow>eps;i=nxt[i]){
if (d[E[i].to]==d[x]+ && E[i].v>eps){
double f=dfs(E[i].to,min(a-flow,E[i].v));
E[i].v-=f;
E[i^].v+=f;
flow+=f;
}
}
if (fabs(flow)<eps) d[x]=-;
return flow;
}
void Dinic(){
while(mklevel()){
F(i,,T) cur[i]=head[i];
ans-=dfs(S,INF);
}
}
void build(double x){
// cout <<"mid="<<x<<endl;
cnt=; memset(head,,sizeof head);
S=,T=n+m+; ans=0.0;
F(i,,n) add(S,i,(double)c[i]*x);
F(i,,m){
ans+=p[i];
add(u[i],i+n,INF);
add(v[i],i+n,INF);
add(i+n,T,p[i]);
}
}
void init(){
n=getint(); m=getint();
F(i,,n) c[i]=getint();
F(i,,m){
u[i]=getint(); v[i]=getint(); p[i]=getint();
}
double l=,r=1e9,mid;
while(r-l>eps){
mid=(l+r)/;
build(mid);
Dinic();
// printf("mid=%f ans=%f\n",mid,ans);
if (ans<eps) r=mid;
else l=mid;
}
printf("%.2f\n",l);
}
}G1; int main(){
#ifndef ONLINE_JUDGE
freopen("A.in","r",stdin);
freopen("A.out","w",stdout);
#endif
G1.init();
return ;
}
B
更神的状压DP……求包括所有点的，边权和最小的边双？。。。
$n\leq 12 ,m\leq 50$，很容易猜到n是指数级……枚举= =而m是多重循环的（由于前面有指数级的枚举，这里大约应该是两重循环吧）
然而并不会2333
看题解&标程：
核心思想是：一个边双可以通过从一个边双（点）开始，不断加链……不断加链得到！
所以就DP枚举啦~令$f[i]$表示点集$i$为一个边双的最小代价，那么枚举$i$的一个子集，令其为一个边双，然后剩余部分组成一条链，加入到这个边双中。
预处理出来：
1.点集S组成一条链，且两端点为x、y的最小边权和
2.点x连向点集S的最小边权和次小边权（用来将（链/点）连入到边双中
//Round 4 B
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
using namespace std;
typedef long long LL;
inline int getint(){
int r=,v=; char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if (ch=='-') r=-;
for(; isdigit(ch);ch=getchar()) v=v*-''+ch;
return r*v;
}
const int N=,INF=<<;
#define CC(a,b) memset(a,b,sizeof(a))
/*******************template********************/ int n,m,bin[N],g[N][][],h[N][][];
int f[N];
struct edge{int x,y,c,next;}E[N];
int head[],cnt;
void add(int x,int y,int c){
E[++cnt]=(edge){x,y,c,head[x]}; head[x]=cnt;
E[++cnt]=(edge){y,x,c,head[y]}; head[y]=cnt;
} inline void getmin(int &a,int b){a=min(a,b);}
inline int fac(int x){
int ans=;
for(x=x&(x-);x;x=x&(x-)) ans++;
return ans;
}
void init(){
m=(<<n)-;
F(i,,m) F(j,,n) F(k,,n) g[i][j][k]=INF;
F(i,,n){
bin[i]=<<(i-);
g[bin[i]][i][i]=;
}
F(i,,cnt){
int x=E[i].x,y=E[i].y,s=bin[x]+bin[y];
g[s][x][y]=min(g[s][x][y],E[i].c);//直接相邻的两点
} F(i,,m)
F(x,,n) F(y,,n)
if ((bin[x]|i)==i && (bin[y]|i)==i)
for(int j=head[y];j;j=E[j].next)
if ((bin[E[j].y]|i)!=i)
getmin(g[i|bin[E[j].y]][x][E[j].y],g[i][x][y]+E[j].c);
//从链的一端向前扩展 F(i,,m) F(j,,n) F(k,,) h[i][j][k]=INF;
F(i,,m)
F(x,,n)
if ((bin[x]|i)!=i)//找个在点集i之外的点x
for(int j=head[x];j;j=E[j].next)
if ((bin[E[j].y]|i)==i){
if (E[j].c<=h[i][x][]){
h[i][x][]=h[i][x][];
h[i][x][]=E[j].c;
}else getmin(h[i][x][],E[j].c);
}//更新从x到i的最短&次短边权
}
void work(){
F(i,,m) f[i]=INF;
F(i,,n) f[bin[i]]=; F(i,,m)
if (fac(i)>=)//元素个数大于2
for(int s=i&(i-);s;s=i&(s-)){
int t=i-s;
F(x,,n) F(y,,n)
if ((bin[x]|s)==s && (bin[y]|s)==s){
if (x==y)
getmin(f[i],f[t]+g[s][x][x]+h[t][x][]+h[t][x][]);
else
getmin(f[i],f[t]+g[s][x][y]+h[t][x][]+h[t][y][]);
}
}
if (f[m]<INF) printf("%d\n",f[m]);
else puts("Impossible");
}
int main(){
#ifndef ONLINE_JUDGE
freopen("B.in","r",stdin);
freopen("B.out","w",stdout);
#endif
int T=getint();
while(T--){
n=getint(); m=getint();
cnt=; CC(head,);
F(i,,m){
int x=getint(),y=getint(),c=getint();
add(x,y,c);
}
init(); work();
}
return ;
}
C
……这个……不想说什么了……其实是【TYVJ 五月图论专项有奖比赛】的C题，而且数据规模还更小了……
然而我个傻逼还是不会做QAQ，直接贴了原来的代码>_>原谅我……
//Round 4 C
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
typedef long long LL;
inline int getint(){
int r=,v=; char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if (ch=='-') r=-;
for(; isdigit(ch);ch=getchar()) v=v*-''+ch;
return r*v;
}
const int N=;
/*******************template********************/
int to[N<<],next[N<<],head[N],cnt;
void add(int x,int y){
to[++cnt]=y; next[cnt]=head[x]; head[x]=cnt;
to[++cnt]=x; next[cnt]=head[y]; head[y]=cnt;
} int n,a[N],f[N][],dep[N],s[N],fa[N],cut;
LL g[N],ans=1e15;
void dfs(int x){
for(int i=head[x];i;i=next[i])
if (to[i]!=fa[x]){
dep[to[i]]=dep[x]+;
fa[to[i]]=x;
dfs(to[i]);
s[x]+=s[to[i]];
if (s[to[i]]>s[f[x][]]) f[x][]=f[x][],f[x][]=to[i];
else if (s[to[i]]>s[f[x][]]) f[x][]=to[i];
g[x]+=g[to[i]]+s[to[i]];
}
}
LL getans(int x,int cnt){
int t=(f[x][]==cut || s[f[x][]]>s[f[x][]]) ? f[x][] : f[x][];
if (*s[t]>cnt) return *s[t]-cnt+getans(t,cnt);
else return ;
}
void dp(int x){
for(int i=head[x];i;i=next[i])
if (to[i]!=fa[x]){
cut=to[i];
for(int j=x;j;j=fa[j]) s[j]-=s[to[i]];
ans=min(ans,g[]-g[to[i]]-(LL)s[to[i]]*dep[to[i]]-getans(,s[])+g[to[i]]-getans(to[i],s[to[i]]));
for(int j=x;j;j=fa[j]) s[j]+=s[to[i]];
dp(to[i]);
}
} int main(){
#ifndef ONLINE_JUDGE
freopen("C.in","r",stdin);
freopen("C.out","w",stdout);
#endif
n=getint();
F(i,,n){
int x=getint(),y=getint();
add(x,y);
}
F(i,,n) s[i]=getint();
dfs();
dp();
printf("%lld\n",ans);
return ;
}