57 条题解

  • 2
    @ 2017-09-04 19:32:18
    #include <cmath>
    #include <queue>
    #include <cstdio>
    #include <cstring>
    #include <iostream>
    
    #define INF 1000000007
    
    using namespace std;
    
    const int Maxn = 101010;
    
    struct node {
        int next, to, cap; double c;
    } e[Maxn];
    
    int xx1[Maxn], xx2[Maxn], yy1[Maxn], yy2[Maxn], n, S = 0, T, tot = 1, h[Maxn], pre[Maxn];
    double dis[Maxn];
    bool vis[Maxn];
    
    double Dis(int x, int y) {
    //  cout << xx1[x] << ' ' << xx2[y] << endl;
        return sqrt((xx1[x] - xx2[y]) * (xx1[x] - xx2[y]) + (yy1[x] - yy2[y]) * (yy1[x] - yy2[y]));
    }
    
    void Link(int x, int y, int p, double c) {e[++tot] = (node){h[x], y, p, c}; h[x] = tot;}
    
    void Add(int x, int y, int p, double c) {Link(x, y, p, c); Link(y, x, 0, -c);}
    
    int Bfs() {
        queue <int> Q;
        for(int i = S; i <= T; ++i) dis[i] = 1e15, vis[i] = 0, pre[i] = 0;
        Q.push(S); dis[S] = 0; vis[S] = 1;
        while(!Q.empty()) {
            int u = Q.front(); Q.pop(); vis[u] = 0;
    //      cout << u << endl;
            for(int i = h[u]; i; i = e[i].next) {
                int v = e[i].to;
                if(e[i].cap && dis[v] > dis[u] + e[i].c) {
                    pre[v] = i; dis[v] = dis[u] + e[i].c;
                    if(!vis[v]) {
                        vis[v] = 1;
                        Q.push(v);
                    }
                }
            }
        }
        return (dis[T] != 1e15);
    }
    
    double Mcmf() {
        double ans = 0;
        while(Bfs()) {
    //      cout << '!';
            int s = INF;
            for(int i = pre[T]; i; i = pre[e[i ^ 1].to]) {
                s = min(s, e[i].cap);
            }
            for(int i = pre[T]; i; i = pre[e[i ^ 1].to]) e[i].cap -= s, e[i ^ 1].cap += s;
            ans += (double)s * dis[T];
        }
        return ans;
    }
    
    int main() {
        scanf("%d", &n); T = 2 * n + 1;
        for(int i = 1; i <= n; ++i) scanf("%d%d", &xx1[i], &yy1[i]);
        for(int i = 1; i <= n; ++i) scanf("%d%d", &xx2[i], &yy2[i]);
    //  cout << xx1[1] << ' ' << xx2[1] << endl;
        for(int i = 1; i <= n; ++i) Add(S, i, 1, 0), Add(i + n, T, 1, 0);
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= n; ++j) {
    //          cout << Dis(i, j) << endl;
                Add(i, j + n, 1, Dis(i, j));
            }
        }
        printf("%.3lf\n", Mcmf());
        return 0;
    }
    
  • 1
    @ 2017-07-17 15:23:43
    #include <cmath>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <iomanip>
    #include <algorithm>
    #include <vector>
    #include <deque>
    #include <limits>
    #include <string>
    #include <sstream>
    using namespace std;
    
    const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;
    
    int n;
    vector<int> e;
    vector<int> pre;
    vector<int> vis;
    vector<vector<int> > cw;
    vector<vector<int> > ce;
    vector<double> f;
    vector<double> u;
    vector<double> m_x;
    vector<double> m_y;
    vector<double> t_x;
    vector<double> t_y;
    vector<vector<double> > c;
    vector<vector<double> > p;
    deque<int> q;
    
    void add_edge_1(int x,int y,double c_v,double p_v)
    {
        cw[x].push_back(y);
        c[x].push_back(c_v);
        p[x].push_back(p_v);
        ce[y].push_back(cw[x].size()-1);
        cw[y].push_back(x);
        c[y].push_back(0);
        p[y].push_back(-p_v);
        ce[x].push_back(cw[y].size()-1);
    }
    
    int bfs_1(int s,int t,double *flow,double *cost)
    {
        f.resize(0);
        f.resize(cw.size(),0);
        f[s]=oo_max;
        e.resize(0);
        e.resize(cw.size(),-1);
        u.resize(0);
        u.resize(cw.size(),oo_max);
        u[s]=0;
        pre.resize(0);
        pre.resize(cw.size(),-1);
        pre[s]=s;
        vis.resize(0);
        vis.resize(cw.size(),0);
        for (q.resize(0),vis[s]=1,q.push_back(s);(!q.empty());vis[q.front()]=0,q.pop_front())
        {
            int now=q.front();
            for (int i=0;i<cw[now].size();i++)
                if (c[now][i]&&u[now]+p[now][i]<u[cw[now][i]])
                {
                    f[cw[now][i]]=min(c[now][i],f[now]);
                    e[cw[now][i]]=i;
                    u[cw[now][i]]=u[now]+p[now][i];
                    pre[cw[now][i]]=now;
                    if (vis[cw[now][i]]==0)
                        vis[cw[now][i]]=1,q.push_back(cw[now][i]);
                }
        }
        (*flow)=f[t];
        (*cost)=u[t];
        return (pre[t]!=-1);
    }
    
    void min_cost_max_flow_1(int s,int t,double *flow,double *cost)
    {
        double temp_flow,temp_cost;
        while (bfs_1(s,t,&temp_flow,&temp_cost))
        {
            for (int i=t;i!=s;i=pre[i])
                c[pre[i]][e[i]]-=temp_flow,c[i][ce[pre[i]][e[i]]]+=temp_flow;
            (*flow)+=temp_flow;
            (*cost)+=temp_cost;
        }
    }
    
    int main()
    {
        while (~scanf("%d",&n))
        {
            cw.resize(0);
            cw.resize(2*n+2);
            ce.resize(0);
            ce.resize(cw.size());
            c.resize(0);
            c.resize(cw.size());
            p.resize(0);
            p.resize(cw.size());
            for (int i=0;i<cw.size();i++)
            {
                cw[i].resize(0);
                ce[i].resize(0);
                c[i].resize(0);
                p[i].resize(0);
            }
            m_x.resize(0);
            m_x.resize(n+1,0);
            m_y.resize(0);
            m_y.resize(n+1,0);
            for (int i=1;i<=n;i++)
            {
                scanf("%lf%lf",&m_x[i],&m_y[i]);
                add_edge_1(0,i,double(1),double(0));
            }
            t_x.resize(0);
            t_x.resize(n+1,0);
            t_y.resize(0);
            t_y.resize(n+1,0);
            for (int i=1;i<=n;i++)
            {
                scanf("%lf%lf",&t_x[i],&t_y[i]);
                add_edge_1(i+n,cw.size()-1,double(1),double(0));
            }
            for (int i=1;i<=n;i++)
                for (int j=1;j<=n;j++)
                    add_edge_1(i,j+n,1,pow(pow((m_x[i]-t_x[j]),double(2))+pow((m_y[i]-t_y[j]),double(2)),double(1)/double(2)));
            double ans_flow=0,ans_cost=0;
            min_cost_max_flow_1(0,c.size()-1,&ans_flow,&ans_cost);
            printf("%.3lf\n",ans_cost);
        }
    }
    
  • 1
    @ 2016-06-07 20:52:01

    网络流可能会好一些,不过集合dp也是可以秒杀的。
    ```c++
    #include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn = 1<<20;
    double const fix = 1e-6;

    struct Po
    {
    int x,y;
    Po(int a=0,int b=0) : x(a),y(b) {}
    };

    double pro_dis(const Po &a,const Po &b)
    {
    return sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) );
    }

    Po missiles[30],target[30];
    double info[maxn];
    int n;

    inline int bitcount(int a)
    {
    return a==0 ? 0 : bitcount(a>>1)+(a&1);
    }

    double dp(int S)
    {
    if(info[S]>=0) return info[S];
    int m = bitcount(S);
    Po now=missiles[m];
    for(int i=0;i<n;i++)
    if(S&(1<<i))
    {
    if(info[S]<0) info[S]= pro_dis(target[i+1],now) + dp(S^(1<<i));
    else info[S] = min(info[S],pro_dis(target[i+1],now) + dp(S^(1<<i)));
    }
    return info[S];
    }

    int main()
    {
    scanf("%d",&n);
    info[0]=0;
    for(int i=1;i<(1<<n);i++)
    info[i]=-1.0;
    for(int i=1;i<=n;i++)
    {
    int a,b;
    scanf("%d%d",&a,&b);
    missiles[i]=Po(a,b);
    }
    for(int i=1;i<=n;i++)
    {
    int a,b;
    scanf("%d%d",&a,&b);
    target[i]=Po(a,b);
    }

    double ans = dp((1<<n)-1);
    printf("%.3lf\n",ans);
    return 0;
    }
    ```

  • 1
    @ 2015-11-14 23:04:30

    最小费用最大流 0 ms
    对于任意一个导弹,将其与所有目标连边(即每个导弹连 n 条边),费用=两点距离,容量=1
    然后加一个源点(指向所有导弹)与一个汇点(所有目标指向它),这些边费用都为0,容量都为1
    然后开始网络流...

  • 1
    @ 2015-02-04 12:24:46

    浮点数的最小费用流写得疼死了....

    ##Code

    db INF=1e20;
    db eps=1e-11;
    bool fequal(db a,db b)
    { return fabs(a-b)<eps; }

    //maxflow

    struct edge
    {
    int in;
    int c;
    db v;
    edge*nxt;
    edge*ptr;
    }pool[100000];
    edge*et=pool;
    edge*eds[1000];
    void addedge(int i,int j,int c,db v)
    {
    et->ptr=et+1;
    et->in=j; et->c=c; et->v=v; et->nxt=eds[i]; eds[i]=et++;
    et->ptr=et-1;
    et->in=i; et->c=0; et->v=-v; et->nxt=eds[j]; eds[j]=et++;
    }
    #define FOREACH_EDGE(i,j) for(edge*i=eds[j];i;i=i->nxt)

    int n;
    int st,ed;

    db cost;
    db dist[1000];
    bool used[1000];
    int DFS(int x,int mi)
    {
    if(x==ed) return mi;
    used[x]=true;
    int res=0; int c;
    FOREACH_EDGE(i,x)
    if(i->c>0 && !used[i->in] && fequal(dist[x]+i->v,dist[i->in]) && ( c=DFS(i->in,min(i->c,mi)) ))
    {
    res+=c;
    i->c-=c;
    i->ptr->c+=c;
    mi-=c;
    cost+=db(c)*i->v;
    if(mi==0) break;
    }
    used[x]=false;
    if(res==0) dist[x]=INF;
    return res;
    }

    int qh,qt;
    int q[4000000];
    db DINIC()
    {
    db res=0.0;

    while(true)
    {
    fillarray(dist,INF,n);
    qh=qt=0;
    q[qt++]=st;
    dist[st]=0;
    while(qh!=qt)
    {
    int&cur=q[qh];
    FOREACH_EDGE(i,cur)
    if( i->c>0 && dist[i->in] > dist[cur] + i->v )
    {
    dist[i->in]=dist[cur]+i->v;
    q[qt++]=i->in;
    }
    qh++;
    }

    if(dist[ed]>=INF) break;

    cost=0;
    if(0==DFS(st,(1<<28)-1)) break;
    res+=cost;
    }

    return res;
    }

    //=================================================

    int ptot;
    int mx[1050];
    int my[1050];
    int ex[1050];
    int ey[1050];

    db dst(int i,int j)
    { return sqrt(db(mx[i]-ex[j])*db(mx[i]-ex[j])+db(my[i]-ey[j])*db(my[i]-ey[j])); }

    //blocks define
    #define MISSILE(i) (i)
    #define ENEMY(i) ((i)+ptot)

    int main()
    {
    ptot=getint();
    for(int i=0;i<ptot;i++)
    mx[i]=getint(),my[i]=getint();
    for(int i=0;i<ptot;i++)
    ex[i]=getint(),ey[i]=getint();

    st=ptot*2;
    ed=st+1;
    n=ed+1;

    for(int i=0;i<ptot;i++)
    for(int j=0;j<ptot;j++)
    addedge(MISSILE(i),ENEMY(j),1,dst(i,j));

    for(int i=0;i<ptot;i++)
    addedge(st,MISSILE(i),1,0.0);

    for(int i=0;i<ptot;i++)
    addedge(ENEMY(i),ed,1,0.0);

    printf("%.3lf\n",DINIC());

    return 0;
    }

  • 0
    @ 2019-04-02 16:50:05

    #include <cmath>
    #include <queue>
    #include <cstdio>
    #include <cstring>
    #include <iostream>

    #define INF 1000000007

    using namespace std;

    const int Maxn = 101010;

    struct node {
    int next, to, cap; double c;
    } e[Maxn];

    int xx1[Maxn], xx2[Maxn], yy1[Maxn], yy2[Maxn], n, S = 0, T, tot = 1, h[Maxn], pre[Maxn];
    double dis[Maxn];
    bool vis[Maxn];

    double Dis(int x, int y) {
    // cout << xx1[x] << ' ' << xx2[y] << endl;
    return sqrt((xx1[x] - xx2[y]) * (xx1[x] - xx2[y]) + (yy1[x] - yy2[y]) * (yy1[x] - yy2[y]));
    }

    void Link(int x, int y, int p, double c) {e[++tot] = (node){h[x], y, p, c}; h[x] = tot;}

    void Add(int x, int y, int p, double c) {Link(x, y, p, c); Link(y, x, 0, -c);}

    int Bfs() {
    queue <int> Q;
    for(int i = S; i <= T; ++i) dis[i] = 1e15, vis[i] = 0, pre[i] = 0;
    Q.push(S); dis[S] = 0; vis[S] = 1;
    while(!Q.empty()) {
    int u = Q.front(); Q.pop(); vis[u] = 0;
    // cout << u << endl;
    for(int i = h[u]; i; i = e[i].next) {
    int v = e[i].to;
    if(e[i].cap && dis[v] > dis[u] + e[i].c) {
    pre[v] = i; dis[v] = dis[u] + e[i].c;
    if(!vis[v]) {
    vis[v] = 1;
    Q.push(v);
    }
    }
    }
    }
    return (dis[T] != 1e15);
    }

    double Mcmf() {
    double ans = 0;
    while(Bfs()) {
    // cout << '!';
    int s = INF;
    for(int i = pre[T]; i; i = pre[e[i ^ 1].to]) {
    s = min(s, e[i].cap);
    }
    for(int i = pre[T]; i; i = pre[e[i ^ 1].to]) e[i].cap -= s, e[i ^ 1].cap += s;
    ans += (double)s * dis[T];
    }
    return ans;
    }

    int main() {
    scanf("%d", &n); T = 2 * n + 1;
    for(int i = 1; i <= n; ++i) scanf("%d%d", &xx1[i], &yy1[i]);
    for(int i = 1; i <= n; ++i) scanf("%d%d", &xx2[i], &yy2[i]);
    // cout << xx1[1] << ' ' << xx2[1] << endl;
    for(int i = 1; i <= n; ++i) Add(S, i, 1, 0), Add(i + n, T, 1, 0);
    for(int i = 1; i <= n; ++i) {
    for(int j = 1; j <= n; ++j) {
    // cout << Dis(i, j) << endl;
    Add(i, j + n, 1, Dis(i, j));
    }
    }
    printf("%.3lf\n", Mcmf());
    return 0;
    }

  • 0
    @ 2016-10-23 14:53:20

    二分图最大权匹配,用KM算法即可。
    没看到“使每个导弹到其目标的距离之和最小。”,一直求最大。。。。对这个,只要取负数最后反转即可。

    //KM
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #define eps 1e-5
    const int INF=0x3f3f3f3f;
    using namespace std;
    int n;
    double w[22][22],lx[22],ly[22],lack;
    int link[22];
    bool visx[22],visy[22];
    struct point{
        int x,y;
    }p[22];
    bool dfs(int x){
        visx[x]=1;
        for(int y=1;y<=n;y++)
        if(!visy[y]){
            double t=lx[x]+ly[y]-w[x][y];
            if(t<eps){
                visy[y]=1;
                if(link[y]==-1||dfs(link[y])){
                    link[y]=x;
                    return 1;
                }
            }else if(lack-eps>t)lack=t;
        }
        return 0;
    }
    int main(){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%d%d",&p[i].x,&p[i].y);
        for(int i=1;i<=n;i++){
            int X,Y;
            scanf("%d%d",&X,&Y);
            for(int j=1;j<=n;j++)
            w[i][j]=-sqrt( pow(p[j].x-X,2.0)+pow(p[j].y-Y,2.0) );
        }
        memset(link,-1,sizeof(link));
        for(int i=1;i<=n;i++)ly[i]=0.000;
        for(int i=1;i<=n;i++){
            lx[i]=INF;
            for(int j=1;j<=n;j++)
            if(w[i][j]-eps>lx[i])lx[i]=w[i][j];
        }
        for(int x=1;x<=n;x++){
            for(;;){
                memset(visx,0,sizeof(visx));
                memset(visy,0,sizeof(visy));
                lack=INF;
                if(dfs(x))break;
                for(int i=1;i<=n;i++){
                    if(visx[i])lx[i]-=lack;
                    if(visy[i])ly[i]+=lack;
                }
            }
        }
        double res=0.000;
        for(int i=1;i<=n;i++)
        res-=w[link[i]][i];
        printf("%.3f\n",res);
        return 0;
    }
    
  • 0
    @ 2014-09-07 17:14:02

    题目略坑。。

  • 0
    @ 2014-07-08 10:29:00

    注意不能d=0,显然会t解

  • 0
    @ 2010-03-05 21:49:57

    20*20的KM?

  • 0
    @ 2009-11-06 20:22:43

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    终于A了,,膜拜K-Boy巨快如闪电。。。

  • 0
    @ 2009-11-01 14:13:33

    我写出来的精度有问题..

    先把费用乘一个10e5 算出结果后再除 才过了的

    用int64记录

  • 0
    @ 2009-10-13 18:04:10

    预处理出所有不相交的直线,然后再搜索,会发现速度巨快如闪电....

    另:最优化也是要加的........

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

  • 0
    @ 2009-09-15 21:39:58

    楼上的是俺的小号。。。

    题解:

    http://lifeich1.spaces.live.com/blog/cns!9AB465A9D807BE22!191.entry

  • 0
    @ 2009-09-12 19:31:47

    费用流(spfa的)和km都没有精度的问题,都是0ms。各写了一遍。

  • 0
    @ 2009-09-06 11:15:51

    极其郁闷..

    把for i:=1 to n do for j:=1 to n do

    改成 for i:=1 to n do for j:=n downto 1 do

    就过了...

    纪念300题

  • 0
    @ 2009-07-30 14:08:41

    先随便弄一个匹配,然后调整。如果x1到y1的距离+x2到y2的距离>x1到y2的距离+x2到y1的距离就交换。

    但是一直90。抓狂。浪费我一大堆提交。

    结果看了这页的题解发现,初始时不要贪心着弄匹配,直接第i个跟第i个相连就行了。还有,for i:=1 to n do for j:=n downto 1 do就Ac了

    大概这个方法不对吧?是拼RP的吧?不清楚,汗……

  • 0
    @ 2009-07-23 09:43:01

    第一次写费用流。。。。

  • 0
    @ 2009-07-21 18:09:29

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    费用流随便写写。。。

  • 0
    @ 2009-04-05 15:36:00

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

信息

ID
1228
难度
7
分类
图结构 | 二分图 点击显示
标签
(无)
递交数
710
已通过
151
通过率
21%
被复制
4
上传者