思路 1.记ans = INF 2.从任意点,用prim做最大生成树,记录最后一次加入到生成树中的点记为s,以及最后一次加入到生成树中的边记为e,记录e的另一端为t。 3.把与s节点相连的所有边权值相加记录为sum,去与ans取最小值更新ans 4.把s和t节点合并,若s和t都对r节点有边,合并后新的节点则是对r有重边。 5.回到步骤2,继续,直到只剩下了1个节点为止。 证明 定理1:sum就是上述的s和t的最小割。 证明 设与s相连的边分别是e1,e2,...,ene_1, e_2,...,e_ne​1​​,e​2​​,...,e​n​​,这些边的另一端分别为p1,p2,...,pnp_1, p_2, ..., p_np​1​​,p​2​​,...,p​n​​ 我们拿第一条边来举例子: 由于已经做了最大生成树,所以p1p_1p​1​​到ttt一定是可以通过最大生成树上的边到达的。 那么,考虑sss经过e1e_1e​1​​到达ttt,这条路径我们现在要让它断开。 可以分成两种情况,第一种情况是断开e1e_1e​1​​,第二种情况是断开p1p_1p​1​​与ttt不通过sss时的其他所有路径。 由于
acm
发表于 2017-08-08 10:01:23 | 条评论 | 阅读次数:115
创建 # config.pySQLALCHEMY_DATABASE_URI = 'mysql://root:123456@127.0.0.1/mc-backend-test'# main.pyfrom flask.ext.sqlalchemy import SQLAlchemydb = SQLAlchemy(blog) # 从flask的app的config创建 model层 class MessageContent(db.Model): __tablename__ = 'message_content' # 对应表的名字 id = db.Column('id', db.Integer, primary_key=True) # 声明主键 user_id = db.Column('user_id', db.Integer, doc="用户id", default=0) group_id = db.Column('group_id', db.Integer, default=0, doc="属于哪一组的消息") created_at = db.Column('c
发表于 2017-07-18 20:38:21 | 条评论 | 阅读次数:250
感觉flask_cache的那个缓存并不是太好用,于是自己撸了一个缓存的装饰器,配合redis实现。 利用这个,就能用来再继续做,得到orm自动缓存的基类等等。 # -*- coding:utf8 -*-import picklefrom app_create import r, config# r是StrictRedisdef cache(id, timeout=config.CACHE_DEFAULT_TIME): def real_decorator(func): answer = None key = '%s%s' % (config.CACHE_PREFIX, id) if r.exists(key): try: answer = pickle.loads(r.get(key)) except: pass def wrapped(*args, **kwargs): if answer is not None:
发表于 2017-07-15 01:45:00 | 条评论 | 阅读次数:83
首先进入venv,然后直接用pip安装celery即可。 celery_server.py # coding: utf-8from celery import Celerymq = Celery('QwbCelery', broker='redis://localhost:6379/0', backend='redis://localhost:6379/0')mq = Celery('QwbCelery')mq.conf.update( CELERY_ACCEPT_CONTENT=['pickle'], CELERY_ENABLE_UTC=True, CELERY_RESULT_BACKEND='redis://localhost:6379/0', CELERYD_LOG_COLOR=False, BROKER_URL='redis://localhost:6379/0', CELERY_TIMEZONE='UTC',)mq.conf.update( CELERY_IMPORTS=[ 'tasks.task1', ]) IMPORTS中
发表于 2017-07-12 13:30:43 | 条评论 | 阅读次数:89
以前装系统的时候,就有点问题,一直没有解决,终于现在系统被我玩坏了,可以重新装啦~ 之前我分了系统盘和数据盘,我们这次装机的目的是把系统盘重装,然后数据盘依然使用以前的。 然后还发现以前系统的内存似乎太大了点,似乎用不了那么多,于是就预留了几十个G,到时候再挂载到需要的地方。 首先在官网下载最新版系统的iso,然后官网有制作启动U盘的工具,先把U盘做好。 做好后,重启电脑,按F2,在选择启动中,把USB对应的那个启动放到最前面,重启后就能开始装系统了 之后的话,把磁盘按下面图的方式挂载就好了 linux-swap为交换分区,通常为内存的大小 把数据盘挂载到/home 建立一个放系统内容的,挂载到/ 建立一个efi做引导,大小通常300MB,不需要设置挂载位置 建立一个分区,大小为500MB,挂载到/boot 然后就一直下一步直到安装完成就好啦~ 安装完后,记得先更新一波源和系统更新。 sudo apt-get update 之后右下角弹出设置,把系统更新一下。 然后再输入 timedatectl set-local-rtc true 然后再去设置时区,这样就解决了双系统时区不正常
发表于 2017-07-01 17:13:45 | 条评论 | 阅读次数:105
首先,在python官网下载MySQL-python的最新版本,下载zip的,解压之后,进入目录,然后 python setup.py install 如果是安装到venv虚拟环境里,需要首先进入到具体的操作目录,然后进入环境中,之后再安装setup.py . venv/bin/activate 之后可能会遇到许多错误.. 错误1: sh: mysql_config: not foundTraceback (most recent call last): File "setup.py", line 15, in <module> metadata, options = get_config() File "/home/zhxia/apps/source/MySQL-python-1.2.3/setup_posix.py", line 43, in get_config libs = mysql_config("libs_r") File "/home/zhxia/apps/source/MySQL-python-1.2.3/setup_posix.py",
发表于 2017-06-24 01:22:50 | 条评论 | 阅读次数:102
http://www.51nod.com/contest/problem.html#!problemId=1873 哇震惊了,竟然可以写的这么骚 # -*- coding:utf8 -*-import sysfrom decimal import *getcontext().prec = 1000 #设置小数点数a, b = raw_input().split()a, b = Decimal(a), int(b)ans = '{:f}'.format(a ** b)if ans[:2] == '0.': ans = ans[1:]while ans[-1:] == '0': ans = ans[:-1]if ans[-1:] == '.': ans = ans[:-1]print ans 直接把float转换成int竟然会有浮点误差!就算是刚读入的也不行 # -*- coding:utf8 -*-import sysa, b = raw_input().split()a, b = int(float(a)*1e6+1e-8), int(b)ans = str(a ** b)n = len(ans
发表于 2017-06-18 00:20:43 | 条评论 | 阅读次数:106
Copyright © 2017 - 2018 qwb's blog
blog.csustacm.com All Rights Reserved
Powered by qwb Contact me