官方解题报告：http://blog.sina.com.cn/s/blog_6bddecdc0102v01l.html
A simple brute force problem. http://acm.hdu.edu.cn/showproblem.php?pid=4971
有n个项目，m个问题，解决某个项目会需要解决一些问题，解决项目挣钱，解决问题花钱，某些问题解决之前需解决其他问题。a之前要做b，b之前要做a，也就是会出现环，需要先缩点，参考有向图强连通分量缩点。对于缩点之后的图，参考最大权闭合图的方法建图，源点s到正权点，流量正权值，原图全连inf流量，负权点到汇点t连负权的绝对值。跑出来的最大流也是最小割，用所有正权减去最小割就是可获得的最大权值。
#include<cstdio>
#include<cstring>
#include<vector>
#include<stack>
#include<queue>
#define mt(a,b) memset(a,b,sizeof(a))
using namespace std;
const int M=;
const int inf=0x3f3f3f3f;
int val[M],cost[M],newcost[M];
vector<int> need[M];
class Tarjan{///有向图强连通分量缩点
static const int ME=M*M;///边的个数
static const int MV=M;///点的个数
int Index,Bcnt,num[MV],belong[MV],dfn[MV],low[MV];
bool instack[MV];
stack<int> s;
void tarjan(int u) {
dfn[u]=low[u]=++Index;
instack[u]=true;
s.push(u);
int v;
for(int i=g.head[u]; ~i; i=g.e[i].next) {
v=g.e[i].v;
if(!dfn[v]) {
tarjan(v);
low[u]=min(low[u],low[v]);
} else if(instack[v]) {
low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u]) {
Bcnt++;
do {
v=s.top();
s.pop();
instack[v]=false;
belong[v]=Bcnt;
num[Bcnt]++;
} while(u!=v);
}
}
public:
struct G {
struct E {
int u,v,next;
} e[ME];
int le,head[MV];
void init() {
le=;
mt(head,-);
}
void add(int u,int v) {
e[le].u=u;
e[le].v=v;
e[le].next=head[u];
head[u]=le++;
}
} g;
public:
void init() {
g.init();
Index=Bcnt=;
mt(num,);
mt(dfn,);
mt(low,);
mt(instack,);
while(!s.empty()) s.pop();
}
void add(int u,int v) {
g.add(u,v);
}
void solve(int n) {///传入点数，点下标1开始
for(int i=; i<=n; i++) {
if(!dfn[i]) {
tarjan(i);
}
}
}
int getbcnt() {///强连通分量的个数
return Bcnt;
}
int getbelong(int id) {///属于哪个分量，分量下标1开始
return belong[id];
}
int getnum(int id) {///某个分量的点的个数
return num[id];
}
}tarjan;
class Dinic { ///最大流 O(MV^2*ME)
typedef int typef;///流量的类型
static const int ME=M*M;///边的个数
static const int MV=M;///点的个数
int temp[MV],cur[MV],level[MV],path[MV];
bool used[MV];
queue<int> q;
typef flow;
bool bfs(int s,int t) {
mt(level,-);
while(!q.empty()) q.pop();
q.push(s);
level[s]=;
while(!q.empty()) {
int u=q.front();
q.pop();
for(int i=g.head[u]; ~i; i=g.e[i].next) {
int v=g.e[i].v;
if(level[v]==-&&g.e[i].flow) {
level[v]=level[u]+;
q.push(v);
if(v==t) return true;
}
}
}
return false;
}
struct G {
struct E {
int u,v,next;
typef flow;
} e[ME];
int le,head[MV];
void init() {
le=;
mt(head,-);
}
void add(int u,int v,typef flow) {
e[le].u=u;
e[le].v=v;
e[le].flow=flow;
e[le].next=head[u];
head[u]=le++;
}
} g;
public:
typef getflow() {
return flow;
}
void init() {
g.init();
}
void add(int u,int v,typef flow) {
g.add(u,v,flow);
g.add(v,u,);
}
void solve(int s,int t) {
int p,tempp;
typef now;
bool flag;
flow=;
while(bfs(s,t)) {
for(int i=; i<MV; i++) {
temp[i]=g.head[i];
used[i]=true;
}
p=;
path[p]=s;
while(p) {
int u=path[p];
if(u==t) {
now=inf;
for(int i=; i<p; i++) {
now=min(now,g.e[cur[path[i]]].flow);
}
flow+=now;
for(int i=; i<p; i++) {
int j=cur[path[i]];
g.e[j].flow-=now;
g.e[j^].flow+=now;
if(!g.e[j].flow) tempp=i;
}
p=tempp;
} else {
flag=false;
for(int i=temp[u]; ~i; i=g.e[i].next) {
int v=g.e[i].v;
if(used[v]&&g.e[i].flow&&level[u]+==level[v]) {
cur[u]=i;
temp[u]=g.e[i].next;
flag=true;
path[++p]=v;
break;
}
}
if(flag) continue;
p--;
used[u]=false;
}
}
}
}
} dinic;
int main(){
int t,n,m;
while(~scanf("%d",&t)){
for(int cas=;cas<=t;cas++){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++){
scanf("%d",&val[i]);
}
for(int i=;i<=m;i++){
scanf("%d",&cost[i]);
}
for(int i=,num,id;i<=n;i++){
scanf("%d",&num);
need[i].clear();
while(num--){
scanf("%d",&id);
need[i].push_back(id+);
}
}
tarjan.init();
for(int i=;i<=m;i++){
for(int j=,op;j<=m;j++){
scanf("%d",&op);
if(op){
tarjan.add(i,j);
}
}
}
tarjan.solve(m);
dinic.init();
for(int i=;i<tarjan.g.le;i++){
int u=tarjan.g.e[i].u;
int v=tarjan.g.e[i].v;
u=tarjan.getbelong(u);
v=tarjan.getbelong(v);
if(u!=v){
dinic.add(u+n,v+n,inf);
}
}
for(int i=;i<=n;i++){
int len=need[i].size();
for(int j=;j<len;j++){
dinic.add(i,n+tarjan.getbelong(need[i][j]),inf);
}
}
int s=,t=n+m+;
int sum=;
for(int i=;i<=n;i++){
dinic.add(s,i,val[i]);
sum+=val[i];
}
mt(newcost,);
for(int i=;i<=m;i++){
newcost[tarjan.getbelong(i)]+=cost[i];
}
for(int i=;i<=tarjan.getbcnt();i++){
dinic.add(i+n,t,newcost[i]);
}
dinic.solve(s,t);
printf("Case #%d: %d\n",cas,sum-dinic.getflow());
}
}
return ;
}
A simple water problem http://acm.hdu.edu.cn/showproblem.php?pid=4974
每次最多贡献2分，结果至少是最大值，偶数就sum/2，奇数还要加一。
#include<cstdio>
#include<algorithm>
using namespace std;
typedef __int64 LL;
int main(){
int t,n,a;
while(~scanf("%d",&t)){
for(int cas=;cas<=t;cas++){
scanf("%d",&n);
int big=;
LL sum=;
while(n--){
scanf("%d",&a);
big=max(big,a);
sum+=a;
}
LL ans=sum/;
if(sum&) ans++;
printf("Case #%d: %I64d\n",cas,max((LL)big,ans));
}
}
return ;
}
A simple probability problem. http://acm.hdu.edu.cn/showproblem.php?pid=4978
这种做法比较好理解。
题目说是有间距为D的等间距的无穷条平行线，考虑一个线段长度为L的概率。题目说点在直径为D的圆内，所以L<=D.
平行时除了一次重合，别的都没有相交，概率约等于0.垂直的概率就是L/D。考虑通用情况，设平行线与我们的线段L夹角为θ。
则要转化成垂直然后计算概率，那么就是长度Lsinθ在D之间的概率。综上所述，对任意夹角θ，有通用公式概率P=L*sin（θ）/D.经检验，0度90度满足公式。
因为是随机放球，相当于夹角θ是随机的，L,D都是定值，那么概率就等于sin（θ）在0到180的均值。因为是随机，所以每个角度等概率，所以是均值。
为了计算sin（θ）的均值，打不出来了。考虑用面积，就是定积分来求。因为面积=定积分=底乘高，如果把函数图像拉直成一个矩形，面积就是y*（x2-x1）。
y就是均值，x1=0，x2=π。那个是派,3.1415926,是弧度中的180度.
求出来发现面积是2,也就是y*(pi-0)=2,那么sin（θ）的均值也就是y就等于2/pi. pi是派 3.14。
L*sin（θ）/D 等于下方结果。
所以官方题解的第一句话证毕。
现在我们的问题是圆内有n个点，他们之间两两间有线段，求和直线相交的概率。
通俗的想，里面的肯定没有外面的好，如果外面的相交的长度肯定大于里面的，这里就可以想到凸包。
然后就套凸包模板。然后点就只剩下凸包上的了。
然后就变成了求凸包和直线相交的概率=P。
接着，凸包要和直线相交，那么必然有凸包上的两条边和直线相交了。因为直线穿过了这个凸包，如果只和一条边相交，那就重合，是边界条件，对概率影响几乎为零，不考虑。
紧接着，凸包和直线相交，不可能穿过3条边，或者更多，因为是凸包。所以我们得到一个朴素的结论，凸包和直线相交的情况，就是有且仅有2条边与直线相交。
定义P i 表示 第i 条边和直线相交的概率。
则我们所求的凸包和直线相交的概率就是 P=1/2* sum(Pi) (i=1,2,...n) 其中pi 是线段 i 与直线相交的概率。我们把所有凸包的边枚举了，把他们的概率加起来。
之所以要除以2，因为一条直线一定会穿过两条边，那么对每一条直线，我们在概率里都算了两次，所以求和后除以2.
P=1/2* sum(Pi) (i=1,2,...n)
记@=3.1415926
我们刚才推出了一条边的概率 Pi =2*Li/(@*D) . 带入上式
P=(1/2) * sum ( 2*Li / ( @ *D ) ) (i=1,2,...n)
除了Li 其他都可以提出来
P = (1/ ( @ * D ) ) * sum( Li ) (i=1,2,...n)
@是派，实在难打，好了 sum Li 不就是周长吗。
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const double pi=acos(-1.0);
const double eps=1e-;
const int M=;
struct point{
double x,y;
}p[M],res[M];
bool operator < (const point &l, const point &r) {
return l.y < r.y || (fabs(l.y- r.y)<eps && l.x < r.x);
}
class ConvexHull { //凸包
bool mult(point sp, point ep, point op) {//>包括凸包边上的点,>=不包括
return (sp.x - op.x) * (ep.y - op.y)>= (ep.x - op.x) * (sp.y - op.y);
}
public:
int graham(int n,point p[],point res[]) {//多边形点个数和点数组，凸包存res
sort(p, p + n);
if (n == ) return ;
res[] = p[];
if (n == ) return ;
res[] = p[];
if (n == ) return ;
res[] = p[];
int top=;
for (int i = ; i < n; i++) {
while (top && mult(p[i], res[top], res[top-])) top--;
res[++top] = p[i];
}
int len = top;
res[++top] = p[n - ];
for (int i = n - ; i >= ; i--) {
while (top!=len && mult(p[i], res[top],res[top-])) top--;
res[++top] = p[i];
}
return top; // 返回凸包中点的个数
}
} gx;
double Distance(point p1,point p2) {
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
int main(){
int t,n,d;
while(~scanf("%d",&t)){
for(int cas=;cas<=t;cas++){
scanf("%d%d",&n,&d);
for(int i=;i<n;i++){
scanf("%lf%lf",&p[i].x,&p[i].y);
}
int lr=gx.graham(n,p,res);
res[lr]=res[];
double sum=;
for(int i=;i<lr;i++){
sum+=Distance(res[i],res[i+]);
}
printf("Case #%d: %.4f\n",cas,sum/pi/d);
}
}
return ;
}
其实我是想说，这种做法比较好理解，虽然不是正解，但只要精度够了，也能过。
上面说过，一条线，长度L，那么概率是 通用公式P=L*sin（θ）/D. 角度是0到180，等可能，而对于凸包，某一个角度和直线相交的概率就是这个角度下凸包最远距离。
如图，在某一个角度θ下，与直线相交的概率就是凸包在与直线垂直的方向上的投影。maxL。 为了求这个投影，可以on的枚举凸包的点，计算到直线的最近距离的点。
然后因为这些点在直线上是递增的。所以取最大的和最小的，就是最远的两个点。然后就可以算出maxl， maxl/D就是当前角度下的概率，我们自定义个增量枚举角度。
对每一个角度都求一个maxl， 最后 sum（maxLi）/num 就是平均长度， 再/D就是概率。
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const double pi=acos(-1.0);
const double eps=1e-;
const int M=;
struct point {
double x,y;
} p[M],res[M];
bool operator < (const point &l, const point &r) {
return l.y < r.y || (fabs(l.y- r.y)<eps && l.x < r.x);
}
class ConvexHull { //凸包
bool mult(point sp, point ep, point op) {//>包括凸包边上的点,>=不包括
return (sp.x - op.x) * (ep.y - op.y)>= (ep.x - op.x) * (sp.y - op.y);
}
public:
int graham(int n,point p[],point res[]) {//多边形点个数和点数组，凸包存res
sort(p, p + n);
if (n == ) return ;
res[] = p[];
if (n == ) return ;
res[] = p[];
if (n == ) return ;
res[] = p[];
int top=;
for (int i = ; i < n; i++) {
while (top && mult(p[i], res[top], res[top-])) top--;
res[++top] = p[i];
}
int len = top;
res[++top] = p[n - ];
for (int i = n - ; i >= ; i--) {
while (top!=len && mult(p[i], res[top],res[top-])) top--;
res[++top] = p[i];
}
return top; // 返回凸包中点的个数
}
} tubao;
double xmult(point p1,point p2,point p0) {
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
double Distance(point p1,point p2) {
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
struct line {
point a,b;
};
point intersection(point u1,point u2,point v1,point v2) {
point ret=u1;
double t=((u1.x-v1.x)*(v1.y-v2.y)-(u1.y-v1.y)*(v1.x-v2.x)) /((u1.x-u2.x)*(v1.y-v2.y)-(u1.y-u2.y)*(v1.x-v2.x));
ret.x+=(u2.x-u1.x)*t;
ret.y+=(u2.y-u1.y)*t;
return ret;
}
point ptoline(point p,line l) {//点到直线上的最近点
point t=p;
t.x+=l.a.y-l.b.y,t.y+=l.b.x-l.a.x;
return intersection(p,t,l.a,l.b);
}
int main() {
int t,n;
double D;
while(~scanf("%d",&t)) {
int cas=;
while(t--) {
scanf("%d%lf",&n,&D);
for(int i=; i<n; i++) {
scanf("%lf%lf",&p[i].x,&p[i].y);
}
int lr=tubao.graham(n,p,res);
double sum=;
int num=;
double add=180.0/;
for(double jiao=; jiao<; jiao+=add) {
double xita=jiao/*pi;
line ll;
ll.a.x=ll.a.y=;
ll.b.x=;
ll.b.y=tan(xita);
point p1=ptoline(res[],ll);
point p2=p1;
for(int i=; i<lr; i++) {
point p3=ptoline(res[i],ll);
p1=max(p1,p3);
p2=min(p2,p3);
}
sum+=Distance(p1,p2);
num++;
}
printf("Case #%d: %.4f\n",cas++,sum/D/num);
}
}
return ;
}
end