CF1519E Off by One
CF1519E Off by One
一、题目
点此看题
二、解法
看到这个题就感觉很像匹配，我们把这个题先转化成图论模型。
我是这样转化的：先把坐标上的点按两个方向都移动一下，算出 x,y 的比值，然后比值相同的点可以连边。但仔细想一想这不是一般图最大匹配吗？做得动就有鬼了
你需要知道：匹配点是不容易的，但是匹配边是容易的。我们不妨把上图点和边的意义互换一下，我们把 x,y 的比值当成点，每个坐标点就代表了连接该图两个点的边，那么每次我们可以匹配两个具有共同点的边。
可以构造给出最优解，答案的上界是每个联通块的边数除 2 下取整求和，考虑构造到这个上界。构造可以考虑 dfs 树，对于当前点 u 如果已有的边数是奇数的话我们把父边划分给当前点，否则把父边留给父亲，dfs 数是不存在交叉边的，返祖边可以全部留给祖先。
时间复杂度 O(n)
#include <cstdio>#include <vector>#include <iostream>#include <map>using namespace std;const int M = 400005;#define make make_pair#define ll long long#define pll pair<ll,ll>int read(){ int x=0,f=1;char c; while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;} while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();} return x*f;
}int n,m,res,d[M];vector<int> g[M],h[M],ans[M];map<pll,int> mp;ll gcd(ll a,ll b){ return !b?a:gcd(b,a%b);
}pll get(ll a,ll b,ll c,ll d){
ll g=gcd(a*d,c*b); return make(a*d/g,c*b/g);
}void dfs(int u,int fa){
d[u]=d[fa]+1;int tmp=-1; for(int i=0;i<g[u].size();i++)
{ int v=g[u][i]; if(d[v])
{ if(d[v]>d[u]) continue; if(v==fa && tmp==-1) tmp=i; else ans[v].push_back(h[u][i]);
} else dfs(v,u);
} if(fa)
{ if(ans[u].size()&1) ans[u].push_back(h[u][tmp]); else ans[fa].push_back(h[u][tmp]);
}
}signed main(){
n=read(); for(int i=1;i<=n;i++)
{ int a=read(),b=read(),c=read(),d=read(); int &x=mp[get(a+b,b,c,d)],&y=mp[get(a,b,c+d,d)]; if(!x) x=++m;if(!y) y=++m;
g[x].push_back(y);g[y].push_back(x);
h[x].push_back(i);h[y].push_back(i);
} for(int i=1;i<=m;i++) if(!d[i]) dfs(i,0); for(int i=1;i<=m;i++)
res+=ans[i].size()/2; printf("%d\n",res); for(int i=1;i<=m;i++) for(int j=1;j<ans[i].size();j+=2) printf("%d %d\n",ans[i][j-1],ans[i][j]);
}