1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #define debug cout 8 using namespace std; 9 const int maxn=4e3+1e2,maxe=8e3+1e2;10 const int inf=0x3f3f3f3f;11 12 int u[maxn],v[maxn],deg[maxn];13 int n1,n2,m,mi=inf;14 15 namespace NetworkFlow {16 int s[maxn],t[maxe],nxt[maxe],f[maxe],cnt;17 int dep[maxn],st,ed;18 inline void coredge(int from,int to,int flow) {19 t[++cnt] = to , f[cnt] = flow , nxt[cnt] = s[from] , s[from] = cnt;20 }21 inline void singledge(int from,int to,int flow) {22 coredge(from,to,flow) , coredge(to,from,0);23 }24 inline bool bfs() {25 memset(dep,-1,sizeof(dep)) , dep[st] = 0;26 queue q; q.push(st);27 while( q.size() ) {28 const int pos = q.front(); q.pop();29 for(int at=s[pos];at;at=nxt[at]) if( f[at] && !~dep[t[at]] ) {30 dep[t[at]] = dep[pos] + 1 , q.push(t[at]);31 }32 }33 return ~dep[ed];34 }35 inline int dfs(int pos,int flow) {36 if( pos == ed ) return flow;37 int ret = 0 , now = 0;38 for(int at=s[pos];at;at=nxt[at]) if( f[at] && dep[t[at]] > dep[pos] ) {39 now = dfs(t[at],min(flow,f[at])) , ret += now , flow -= now , f[at] -= now , f[at^1] += now;40 if( !flow ) return ret;41 }42 if( !ret ) dep[pos] = -1;43 return ret;44 }45 inline int dinic() {46 int ret = 0;47 while( bfs() ) ret += dfs(st,inf);48 return ret;49 }50 inline void reset() {51 memset(s,0,sizeof(s)) , cnt = 1;52 }53 }54 55 inline void build(int k) {56 NetworkFlow::reset() , NetworkFlow::st = n1 + n2 + 1 , NetworkFlow::ed = n1 + n2 + 2;57 for(int i=1;i<=m;i++) NetworkFlow::singledge(n1+v[i],u[i],1);58 for(int i=1;i<=n1;i++) NetworkFlow::singledge(i,NetworkFlow::ed,deg[i]-k);59 for(int i=n1+1;i<=n1+n2;i++) NetworkFlow::singledge(NetworkFlow::st,i,deg[i]-k);60 }61 inline void printans() {62 static int seq[maxn],sql; sql = 0;63 using namespace NetworkFlow; dinic();64 for(int i=1;i<=m;i++) if( f[i<<1] ) seq[++sql] = i;65 sort(seq+1,seq+1+sql) , printf("%d ",sql);66 for(int i=1;i<=sql;i++) printf("%d ",seq[i]);67 putchar('\n');68 }69 70 inline int getint() {71 int ret = 0 , ch;72 while( !isdigit(ch=getchar()) );73 do ret = ret * 10 + ch - '0'; while( isdigit(ch=getchar()) );74 return ret;75 }76 77 int main() {78 n1 = getint() , n2 = getint() , m = getint();79 for(int i=1;i<=m;i++) ++deg[u[i]=getint()] , ++deg[n1+(v[i]=getint())];80 for(int i=1;i<=n1+n2;i++) mi = min( mi , deg[i] );81 for(int i=0;i<=mi;i++) build(i) , printans();82 return 0;83 }
(后面j是在枚举能覆盖这个点的圆，后面乘的是这个圆被统计的次数)我们令:
显然关于x的k次多项式的前缀和或有上界的后缀和都是一个关于x的k+1次多项式。所以这个s我们能拉格朗日插值。那么我们的公式能化为:
我们令:
就是一个把x当做常数，关于y的函数了。我们理性分析一下，S(x)是关于x的3次多项式，那么S(x^2+y^2)就是关于y的6次多项式，而这个东西是S(x^2+y^2)的前缀和，就是关于y的7次多项式喽。于是我们又能大力拉格朗日插值......然后我们枚举x，这题就做完了......复杂度O(sqrt(m))，常数巨大，最后一个点要7s......代码: