Hubtown

时间限制: 10 Sec 内存限制: 256 MB

题目描述

Hubtown is a large Nordic city which is home to n citizens. Every morning, each of its citizens wants to travel to the central hub from which the city gets its name, by using one of the m commuter trains which pass through the city. Each train line is a ray (i.e., a line segment which extends infinitely long in one direction), ending at the central hub, which is located at coordinates (0, 0). However, the train lines have limited capacity (which may vary between train lines), so some train lines may become full, leading to citizens taking their cars instead of commuting. The city council wishes to minimize the number of people who go by car. In order to do this, they will issue instructions stating which citizens are allowed to take which train.
A citizen will always take the train line which is of least angular distance from its house. However, if a citizen is exactly in the middle between two train lines, they are willing to take either of them, and city council can decide which of the two train lines the citizen should use.
See Figure H.1 for an example.

Figure H.1: Illustration of Sample Input 1. The dashed arrows indicate which train lines the citizens are closest to (note that we are measuring angular distances, not Euclidean distance).
Your task is to help the council, by finding a maximum size subset of citizens who can go by train in the morning to the central hub, ensuring that each of the citizens take one of the lines they are closest to, while not exceeding the capacity of any train line. For this subset, you should also print what train they are to take.

输入

The first line of input contains two integers n and m, where 0 ≤ n ≤ 200 000 is the number of citizens, and 1 ≤ m ≤ 200 000 is the number of train lines.
The next n lines each contain two integers x and y, the Cartesian coordinates of a citizen’s home. No citizen lives at the central hub of the city.
Then follow m lines, each containing three integers x, y, and c describing a train line, where (x, y) are the coordinates of a single point (distinct from the central hub of the city) which the train line passes through and 0 ≤ c ≤ n is the capacity of the train line. The train line is the ray starting at (0, 0) and passing through (x, y).
All coordinates x and y (both citizens’ homes and the points defining the train lines) are bounded by 1000 in absolute value. No two train lines overlap, but multiple citizens may live at the same coordinates.

输出

First, output a single integer s – the maximum number of citizens who can go by train. Then,output s lines, one for each citizen that goes by train. On each line, output the index of the citizen followed by the index of the train line the citizen takes. The indices should be zero-indexed (i.e.,between 0 and n − 1 for citizens, and between 0 and m − 1 for train lines, respectively), using the same order as they were given in the input.

样例输入

样例输出

题意：n个人，m个铁轨，每个人要到最近的铁轨去，若最近的有两个可二选一，每个铁轨能承受的人数有限，问最多多少个人可以到铁轨上。

做法：先对人和铁轨一起进行极角排序，然后记录一下距离人最近的上下两个铁轨，之后建图跑最大流。具体细节在代码中说明。

此外，这题能跑最大流是因为网络流跑二分图匹配的时间复杂度是 O(m*sqrt(n)),而且实际编程中速度会更快。

#include<bits/stdc++.h>
#define N 400050
#define M 2000050
using namespace std;
typedef struct
{
    int v;
    int flow;
} ss;

ss edg[M];
vector<int>edges[N];
int now_edges=0;

void addedge(int u,int v,int flow)
{
   // printf("          %d %d %d
",u,v,flow);
    edges[u].push_back(now_edges);
    edg[now_edges++]=(ss)
    {
        v,flow
    };
    edges[v].push_back(now_edges);
    edg[now_edges++]=(ss)
    {
        u,0
    };
}

int dis[N],S,T;
bool bfs()
{
    memset(dis,0,sizeof(dis));
    queue<int>q;
    q.push(S);
    dis[S]=1;

    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        int Size=edges[now].size();

        for(int i=0; i<Size; i++)
        {
            ss e=edg[edges[now][i]];
            if(e.flow>0&&dis[e.v]==0)
            {
                dis[e.v]=dis[now]+1;
                q.push(e.v);
            }
        }
    }
    if(dis[T]==0)
        return 0;
    return 1;

}
int current[N];
int dfs(int now,int maxflow)
{
    if(now==T)
        return maxflow;
    int Size=edges[now].size();
    for(int i=current[now]; i<Size; i++)
    {
        current[now]=i;
        ss &e=edg[edges[now][i]];

        if(e.flow>0&&dis[e.v]==dis[now]+1)
        {
            int Flow=dfs(e.v,min(maxflow,e.flow));

            if(Flow)
            {
                e.flow-=Flow;
                edg[edges[now][i]^1].flow+=Flow;
                return Flow;
            }
        }
    }
    return 0;
}

int dinic()
{
    int ans=0,flow;
    while(bfs())
    {
        memset(current,0,sizeof(current));
        while(flow=dfs(S,INT_MAX/2))
            ans+=flow;
    }
    return ans;
}

struct orz  //铁轨和人的统一结构体，value<0为人，value>0为铁轨
{
    int value,number;
    int x,y,sgn;

    void setxy(int a,int b)
    {
        x=a;
        y=b;
        if(!x)sgn=y>0;
        else sgn=x>0;
    }
};

int cross(int x1,int y1,int x2,int y2)//计算叉积
{
    return (x1*y2-x2*y1);
}

int compare(orz a,orz b,orz c)//计算极角
{
    return cross((b.x-a.x),(b.y-a.y),(c.x-a.x),(c.y-a.y));
}

bool cmp(orz a,orz b)
{
    if(a.sgn!=b.sgn)return a.sgn<b.sgn;
    orz c;//原点
    c.x = 0;
    c.y = 0;
    if(compare(c,a,b)==0)//计算叉积，函数在上面有介绍，如果叉积相等，按照X从小到大排序
        return a.number>b.number;
    else
        return compare(c,a,b)<0;
}


bool point_on_line(orz a,orz b)
{
    int d1=__gcd(abs(a.x),abs(a.y)),d2=__gcd(abs(b.x),abs(b.y));
    return (a.x/d1==b.x/d2)&&(a.y/d1==b.y/d2);
}

const long double epsss=1e-10;

struct Point
{
    int x,y;
    Point() {}
    Point(int _x,int _y)
    {
        x=_x,y=_y;
    }
};
struct Pointd
{
    long double x,y;
    Pointd() {}
    Pointd(long double _x,long double _y)
    {
        x=_x,y=_y;
    }
};

int cross(const Point&a,const Point&b)
{
    return a.x*b.y-a.y*b.x;
}

long double crossd(const Pointd&a,const Pointd&b)
{
    return a.x*b.y-a.y*b.x;
}

int sig(int x)
{
    if(x==0)
        return 0;
    return x>0?1:-1;
}

int sigd(long double x)
{
    if(fabs(x)<epsss)
        return 0;
    return x>0?1:-1;
}

int distance_cmp(const orz&_a,const orz&_b,const orz&_c)//判断点a距离哪一条射线近
{
    Point a(_a.x,_a.y);
    Point b(_b.x,_b.y);
    Point c(_c.x,_c.y);
    Point d;
    if(!cross(b,c))
    {
        d=Point(-b.y,b.x);
        if(!cross(a,d))
            return 0;
        if(sig(cross(d,a))==sig(cross(d,b)))
            return -1;
        return 1;
    }
    long double L=sqrt(b.x*b.x+b.y*b.y);
    long double R=sqrt(c.x*c.x+c.y*c.y);
    Pointd aa(a.x,a.y);
    Pointd bb(b.x,b.y);
    Pointd cc(c.x,c.y);
    Pointd dd(d.x,d.y);
    bb.x*=R;
    bb.y*=R;
    cc.x*=L;
    cc.y*=L;
    dd=Pointd(bb.x+cc.x,bb.y+cc.y);
    if(!sigd(crossd(aa,dd)))
        return 0;
    if(sigd(crossd(dd,aa))==sigd(crossd(dd,bb)))
        return -1;
    return 1;
}

orz allpoint[N*2];
int up[N],down[N];

int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    S=n+m+1;
    T=n+m+2;

    for(int i=1; i<=n; i++)
    {
        int x,y;
        scanf("%d %d",&x,&y);
        allpoint[i].setxy(x,y);
        allpoint[i].value=-1;
        allpoint[i].number=i;
        addedge(S,i,1);
    }

    for(int i=1; i<=m; i++)
    {
        int x,y,z;
        scanf("%d %d %d",&x,&y,&z);
        allpoint[i+n].setxy(x,y);
        allpoint[i+n].value=z;
        allpoint[i+n].number=i+n;
        addedge(i+n,T,z);
    }

    sort(allpoint+1,allpoint+1+n+m,cmp);//对人和铁轨一起进行极角排序

    for(int i=n+m;i>=1;i--)if(allpoint[i].value>=0){down[0]=i;break;} //寻找最后一个铁轨
    for(int i=1;i<=n+m;i++)
    {
        down[i]=down[i-1];
        if(allpoint[i].value>=0)down[i]=i;
    }

    for(int i=1;i<=n+m;i++)if(allpoint[i].value>=0){up[n+m+1]=i;break;}//寻找第一个铁轨
    for(int i=n+m;i>=1;i--)
    {
        up[i]=up[i+1];
        if(allpoint[i].value>=0)up[i]=i;
    }

    for(int i=1;i<=n+m;i++)
    if(allpoint[i].value<0)
    {
        int a=up[i],b=down[i];

        if(a==b)addedge(allpoint[i].number,allpoint[a].number,1);
        else
        if(point_on_line(allpoint[i],allpoint[a]))addedge(allpoint[i].number,allpoint[a].number,1);
        else
        if(point_on_line(allpoint[i],allpoint[b]))addedge(allpoint[i].number,allpoint[b].number,1);
        else
        {
            int t=distance_cmp(allpoint[i],allpoint[a],allpoint[b]);
            if(t<=0)addedge(allpoint[i].number,allpoint[a].number,1);
            if(t>=0)addedge(allpoint[i].number,allpoint[b].number,1);
        }
    }

    int sum=dinic();
    printf("%d
",sum);
    for(int i=1; i<=n; i++)
    {
        int Size=edges[i].size();
        for(int j=0; j<Size; j++)
        {
            if(edg[edges[i][j]^1].flow&&edg[edges[i][j]].v!=S)//注意这里要判一下另一个点是不是起点
            {
                printf("%d %d
",i-1,edg[edges[i][j]].v-n-1);
                break;
            }
        }
    }
 return 0;
}

View Code