57 条题解
-
2
sssSSSay LV 10 @ 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
Sky1231 (sky1231) LV 10 @ 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); } }-
很H2O的题
-
-
1
网络流可能会好一些，不过集合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
wang_yanheng LV 10 @ 2015-11-14 23:04:30
最小费用最大流 0 ms
对于任意一个导弹，将其与所有目标连边（即每个导弹连 n 条边），费用=两点距离，容量=1
然后加一个源点（指向所有导弹）与一个汇点（所有目标指向它），这些边费用都为0，容量都为1
然后开始网络流... -
1
浮点数的最小费用流写得疼死了....
##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
#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
二分图最大权匹配,用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
Silence•轩辕•寂 LV 10 @ 2014-09-07 17:14:02
题目略坑。。
-
0
mintalfance LV 10 @ 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
预处理出所有不相交的直线，然后再搜索，会发现速度巨快如闪电....
另：最优化也是要加的........
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms -
0
-
0
fammiebright LV 9 @ 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
lijian3256 LV 10 @ 2009-07-23 09:43:01
第一次写费用流。。。。
-
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
费用流随便写写。。。 -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
sssSSSay
LV 10
@ 2017-09-04 19:32:18
