2014 Multi-University Training Contest 10

 官方解题报告：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=128;
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=0;
            mt(head,-1);
        }
        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=0;
        mt(num,0);
        mt(dfn,0);
        mt(low,0);
        mt(instack,0);
        while(!s.empty()) s.pop();
    }
    void add(int u,int v) {
        g.add(u,v);
    }
    void solve(int n) {///传入点数，点下标1开始
        for(int i=1; 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,-1);
        while(!q.empty()) q.pop();
        q.push(s);
        level[s]=1;
        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]==-1&&g.e[i].flow) {
                    level[v]=level[u]+1;
                    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=0;
            mt(head,-1);
        }
        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,0);
    }
    void solve(int s,int t) {
        int p,tempp;
        typef now;
        bool flag;
        flow=0;
        while(bfs(s,t)) {
            for(int i=0; i<MV; i++) {
                temp[i]=g.head[i];
                used[i]=true;
            }
            p=1;
            path[p]=s;
            while(p) {
                int u=path[p];
                if(u==t) {
                    now=inf;
                    for(int i=1; i<p; i++) {
                        now=min(now,g.e[cur[path[i]]].flow);
                    }
                    flow+=now;
                    for(int i=1; i<p; i++) {
                        int j=cur[path[i]];
                        g.e[j].flow-=now;
                        g.e[j^1].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]+1==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=1;cas<=t;cas++){
            scanf("%d%d",&n,&m);
            for(int i=1;i<=n;i++){
                scanf("%d",&val[i]);
            }
            for(int i=1;i<=m;i++){
                scanf("%d",&cost[i]);
            }
            for(int i=1,num,id;i<=n;i++){
                scanf("%d",&num);
                need[i].clear();
                while(num--){
                    scanf("%d",&id);
                    need[i].push_back(id+1);
                }
            }
            tarjan.init();
            for(int i=1;i<=m;i++){
                for(int j=1,op;j<=m;j++){
                    scanf("%d",&op);
                    if(op){
                        tarjan.add(i,j);
                    }
                }
            }
            tarjan.solve(m);
            dinic.init();
            for(int i=0;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=1;i<=n;i++){
                int len=need[i].size();
                for(int j=0;j<len;j++){
                    dinic.add(i,n+tarjan.getbelong(need[i][j]),inf);
                }
            }
            int s=0,t=n+m+1;
            int sum=0;
            for(int i=1;i<=n;i++){
                dinic.add(s,i,val[i]);
                sum+=val[i];
            }
            mt(newcost,0);
            for(int i=1;i<=m;i++){
                newcost[tarjan.getbelong(i)]+=cost[i];
            }
            for(int i=1;i<=tarjan.getbcnt();i++){
                dinic.add(i+n,t,newcost[i]);
            }
            dinic.solve(s,t);
            printf("Case #%d: %d
",cas,sum-dinic.getflow());
        }
    }
    return 0;
}

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=1;cas<=t;cas++){
            scanf("%d",&n);
            int big=0;
            LL sum=0;
            while(n--){
                scanf("%d",&a);
                big=max(big,a);
                sum+=a;
            }
            LL ans=sum/2;
            if(sum&1) ans++;
            printf("Case #%d: %I64d
",cas,max((LL)big,ans));
        }
    }
    return 0;
}

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-8;
const int M=128;
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 == 0) return 0;
        res[0] = p[0];
        if (n == 1) return 1;
        res[1] = p[1];
        if (n == 2) return 2;
        res[2] = p[2];
        int top=1;
        for (int i = 2; i < n; i++) {
            while (top && mult(p[i], res[top], res[top-1])) top--;
            res[++top] = p[i];
        }
        int len = top;
        res[++top] = p[n - 2];
        for (int i = n - 3; i >= 0; i--) {
            while (top!=len && mult(p[i], res[top],res[top-1])) 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=1;cas<=t;cas++){
            scanf("%d%d",&n,&d);
            for(int i=0;i<n;i++){
                scanf("%lf%lf",&p[i].x,&p[i].y);
            }
            int lr=gx.graham(n,p,res);
            res[lr]=res[0];
            double sum=0;
            for(int i=0;i<lr;i++){
                sum+=Distance(res[i],res[i+1]);
            }
            printf("Case #%d: %.4f
",cas,sum/pi/d);
        }
    }
    return 0;
}

 其实我是想说，这种做法比较好理解，虽然不是正解，但只要精度够了，也能过。

上面说过，一条线，长度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-8;
const int M=128;
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 == 0) return 0;
        res[0] = p[0];
        if (n == 1) return 1;
        res[1] = p[1];
        if (n == 2) return 2;
        res[2] = p[2];
        int top=1;
        for (int i = 2; i < n; i++) {
            while (top && mult(p[i], res[top], res[top-1])) top--;
            res[++top] = p[i];
        }
        int len = top;
        res[++top] = p[n - 2];
        for (int i = n - 3; i >= 0; i--) {
            while (top!=len && mult(p[i], res[top],res[top-1])) 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=1;
        while(t--) {
            scanf("%d%lf",&n,&D);
            for(int i=0; i<n; i++) {
                scanf("%lf%lf",&p[i].x,&p[i].y);
            }
            int lr=tubao.graham(n,p,res);
            double sum=0;
            int num=0;
            double add=180.0/5000;
            for(double jiao=0; jiao<180; jiao+=add) {
                double xita=jiao/180*pi;
                line ll;
                ll.a.x=ll.a.y=0;
                ll.b.x=1;
                ll.b.y=tan(xita);
                point p1=ptoline(res[0],ll);
                point p2=p1;
                for(int i=1; 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
",cas++,sum/D/num);
        }
    }
    return 0;
}

end