补到两道十分有印象的题目。
Contest of Rope Pulling
这题做法很巧妙。
题目大意：给定a,b两个数组，分别有n和m组的（wi,vi）。要求从两个数组中分别选出一个子数组，使得两个子数组的wi和相同，并使总的vi之和最大。
首先一看是有关于价值和容量，可以想到用背包解题。但是两个背包建起来复杂度会到达O（1000*1000*（n+m）*T）会超时。于是我们可以想办法合并一个背包，把b数组的wi都变为负数，那么如果两个子数组的wi会相同，则它们的答案会存储在dp[0]，然而如果按照先a数组再b数组这样子去遍历，这个复杂度也还是可能会超时。
这时，一个十分巧妙的操作，将ab数组合起来随机化一遍！这样子操作，不会像先a数组再b数组遍历这种，造成全部 wi 相加过大，要遍历的范围过多从而超时的情况。
然而不知什么原因，无限RE……
Go Running
这题做法没想到竟然用网络流做。
把当前的位置和时刻当作坐标系上的一个点，如果往左跑或往右跑，即相当于作一条斜率为-1或1的直线，如果一条直线交于两个点，说明这两个位置可能是同一个人跑出来的。
于是一个点要么是属于斜率为-1的直线①，要么属于斜率为1的直线②。
建图，直线①直线②之间连一条容量为1的边，各自连接超级源点与汇点的点之间也要连一条容量为1的边，于是这题就变成了二分图匹配问题。
#include <bits/stdc++.h> #define debug freopen("r.txt","r",stdin) #define mp make_pair #define ri register int #define pb push_back using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 1e6+10; const int INF = 0x3f3f3f3f; const int mod = 1e9+7; const int N=1e6+10; inline ll read(){ll s=0,w=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();} while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar(); return s*w;} ll qpow(ll p,ll q){return (q&1?p:1)*(q?qpow(p*p%mod,q/2):1)%mod;} struct FLOW{ struct edge{int to,w,nxt;}; vector<edge> a; int head[N]; int cur[N]; int n,s,t; queue<int> q; int dep[N],gap[N]; void ae(int x,int y,int w){ a.push_back({y,w,head[x]}); head[x]=a.size()-1; } bool bfs(){ fill(dep,dep+n,-1); dep[t]=0; fill(gap,gap+n,0); gap[0]=1; q.push(t); while(!q.empty()){ int x=q.front(); q.pop(); for(int i=head[x];i!=-1;i=a[i].nxt){ int p=a[i].to; if(dep[p]!=-1)continue; dep[p]=dep[x]+1; q.push(p); gap[dep[p]]++; } } return dep[s]!=-1; } int dfs(int x,int fl){ int now,ans=0; if(x==t)return fl; for(int i=cur[x];i!=-1;i=a[i].nxt){ cur[x]=i; int p=a[i].to; if(a[i].w && dep[p]+1==dep[x]) if((now=dfs(p,min(fl,a[i].w)))){ a[i].w-=now; a[i^1].w+=now; ans+=now,fl-=now; if(fl==0)return ans; } } gap[dep[x]]--; if(gap[dep[x]]==0)dep[s]=n; dep[x]++; gap[dep[x]]++; return ans; } void init(int _n){ n=_n+1; a.clear(); fill(head,head+n,-1); } int solve(int _s,int _t){ //返回最大流 s=_s,t=_t; int ans=0; if(bfs()) while(dep[s]<n){ copy(head,head+n,cur); ans+=dfs(s,INF); } return ans; } }flow; void add(int x,int y,int w){flow.ae(x,y,w),flow.ae(y,x,0);} //先flow.init(n)，再add添边，最后flow.solve(s,t). map<int,int> mapp1,mapp2; int t,n,s,i,T,x,xleft[maxn],xright[maxn],cnt1,cnt2; int main() { T=read(); while (T--) { n=read(); s=cnt1=cnt2=0; for (i=1;i<=n;i++) { t=read(),x=read(); xleft[i]=x-t; xright[i]=x+t; if (!mapp1[xleft[i]]) mapp1[xleft[i]]=++cnt1; if (!mapp2[xright[i]]) mapp2[xright[i]]=++cnt2; } t=cnt1+cnt2+1; flow.init(t); for (i=1;i<=cnt1;i++) add(s,i,1); for (i=1;i<=n;i++) add(mapp1[xleft[i]],mapp2[xright[i]]+cnt1,1); for (i=1;i<=cnt2;i++) add(i+cnt1,t,1); cout<<flow.solve(s,t)<<endl; mapp1.clear(); mapp2.clear(); } return 0; }