差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:namespace:牛客多校第一场 [2020/07/16 09:55]
great_designer [H]
+++ 2020-2021:teams:namespace:牛客多校第一场 [2020/07/17 17:17] (当前版本)
serein [J]
@@ 行 170: / 行 170: @@
 后来得知的一个结论是，对于两个循环字符串字典序比较，s循环大于t循环，等价于st大于ts。这可真是有趣的结论，大概比这个暴力算法更优吧。
+没错，把字符串的循环类比为26进制的无限循环小数，很nice的解法。
 =====I=====
@@ 行 461: / 行 465: @@
 </code>
 </hidden>
+贴一下标程的做法。
+<code>
+static inline int inv(int a) {
+  return a == 1 ? 1 : MOD - 1LL * (MOD / a) * inv(MOD % a) % MOD;
+}
+//求数论倒数的函数并使用内联提高运行效率
+</code>
 =====A=====
@@ 行 600: / 行 613: @@
     return 0;
 }
+</code>
+</hidden>
+=====H=====
+快速读入与费用流。
+每条边的费用已知，容量在每次询问时给出，每次询问求流出1单位的最小费用。
+可以先假设每条边容量为1，每次给出具体容量时再做调整。
+<hidden>
+<code C++>
+#include<stdio.h>
+#include<algorithm>
+#include<vector>
+#include<queue>
+using namespace std;
+int read()
+{
+	int 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;
+}
+long long gcd(long long a,long long b)
+{
+	return b==0?a:gcd(b,a%b);
+}
+long long sum[2005];
+int n,m,q,num;
+int head[2005],dis[2005],h[2005],PrePoint[2005],PreEdge[2005];
+vector<int> mcost;
+struct node
+{
+    int u,v,f,w,nxt;
+};
+struct node edge[2005];
+void addedge(int x,int y,int f,int z)
+{
+    edge[num].u=x;
+    edge[num].v=y;
+    edge[num].f=f;
+    edge[num].w=z;
+    edge[num].nxt=head[x];
+    head[x]=num++;
+}
+void add(int u,int v,int w,int c)
+{
+    addedge(u,v,w,c);
+    addedge(v,u,0,-c);
+}
+int MCMF(int s,int t)
+{
+    int ansflow=0;
+    int i;
+    for(i=1;i<=n;i++)
+	{
+		h[i] = 0;
+	}
+    while(1)
+    {
+        priority_queue<pair<int,int> >q;
+        for(i=1;i<=n;i++)
+		{
+			dis[i] = 1<<30;
+		}
+        dis[s]=0;
+        q.push(make_pair(0,s));
+        while(q.size()!=0)
+        {
+            pair<int,int> p=q.top();
+			q.pop();
+            if(-p.first!=dis[p.second])
+			{
+				continue;
+			}
+            if(p.second==t)
+			{
+				break;
+			}
+            for(i=head[p.second];i!=-1;i=edge[i].nxt)
+            {
+                int nowcost=edge[i].w+h[p.second]-h[edge[i].v];
+                if(edge[i].f>0&&dis[edge[i].v]>dis[p.second]+nowcost)
+                {
+                    dis[edge[i].v]=dis[p.second]+nowcost;
+                    q.push(make_pair(-dis[edge[i].v],edge[i].v));
+                    PrePoint[edge[i].v]=p.second;
+                    PreEdge[edge[i].v]=i;
+                }
+            }
+        }
+        if(dis[t]==1<<30)
+		{
+			break;
+		}
+        for(i=1;i<=n;i++)
+		{
+			h[i]+=dis[i];
+		}
+        int nowflow=1<<30;
+        int now;
+        for(now=t;now!=s;now=PrePoint[now])
+        {
+        	nowflow=min(nowflow,edge[PreEdge[now]].f);
+		}
+        for(now=t;now!=s;now=PrePoint[now])
+        {
+        	edge[PreEdge[now]].f-=nowflow;
+            edge[PreEdge[now]^1].f+=nowflow;
+		}
+        ansflow+=nowflow;
+        mcost.push_back(h[t]);
+    }
+    return ansflow;
+}
+int main()
+{
+    long long u,v,c;
+    while(~scanf("%d%d",&n,&m))
+	{
+		int i;
+        for(i=1;i<=n;i++)
+		{
+			head[i] = -1;
+		}
+        num = 2;
+        mcost.clear();
+        int s = 1,t = n;
+        for(i=1;i<=m;i++)
+		{
+            u = read();
+            v = read();
+            c = read();
+            add(u,v,1,c);
+        }
+        int maxflow = MCMF(s,t);
+        sort(mcost.begin(),mcost.end());
+        int sz = mcost.size();
+        for(i=1;i<=sz;i++)
+		{
+			sum[i] = sum[i-1] + mcost[i-1];
+		}
+        int q = read();
+        while(q--)
+		{
+            u = read();
+			v = read();
+            if(u*maxflow<v)
+			{
+				printf("NaN\n");
+			}
+            else
+			{
+                int L = 1,R = sz,pos;
+                while(L<=R)
+				{
+                    int mid = (L+R)>>1;
+                    if(u*mid >= v)
+					{
+						pos = mid;
+						R=mid-1;
+					}
+                    else
+					{
+						L = mid+1;
+					}
+                }
+                long long a = u*sum[pos-1];
+                long long o = (v-u*(pos-1)) * (sum[pos] - sum[pos-1]);
+                a = a+o;
+                long long g = gcd(a,v);
+                a /= g;
+				v /= g;
+                printf("%lld/%lld\n",a,v);
+            }
+        }
+    }
+    return 0;
+}
 </code>

CVBB ACM Team

用户工具

站点工具

差别

页面工具